NO2——最短路径

【Dijkstra算法】

• 复杂度O(n²) 
• 权值必须非负

/*    求出点beg到所有点的最短路径    */ 
//    邻接矩阵形式 
//    n：图的顶点数
//    cost[][]：邻接矩阵 
//    pre[i]记录beg到i路径上的父结点，pre[beg]=-1
//    返回：各点的最短路径lowcost[]以及路径pre[]
const int maxn=1010; 
const int INF=0x3f3f3f3f;        //防止后面溢出，这个不能太大 
bool vis[maxn]; 
int pre[maxn]; 
void Dijkstra(int cost[][maxn],int lowcost[],int n,int beg) 
{ 
  for(int i=0;i<n;i++) 　　　　　　//点的编号从0开始
  { 
    lowcost[i]=INF;vis[i]=false;pre[i]=-1; 
  } 
  lowcost[beg]=0; 
  for(int j=0;j<n;j++) 
  { 
    int k=-1; 
    int Min=INF; 
    for(int i=0;i<n;i++) 
      if(!vis[i]&&lowcost[i]<Min) 
      { 
        Min=lowcost[i]; 
        k=i; 
      } 
    if(k==-1)break; 
    vis[k]=true; 
    for(int i=0;i<n;i++) 
      if(!vis[i]&&lowcost[k]+cost[k][i]<lowcost[i]) 
      { 
        lowcost[i]=lowcost[k]+cost[k][i]; 
        pre[i]=k; 
      } 
  } 
} 

【Dijkstra算法+堆优化】

• 复杂度O（E*logE）
• 使用优先队列优化Dijkstra算法

//注意对vector<Edge>E[MAXN]进行初始化后加边
const int INF=0x3f3f3f3f; 
const int maxn=1000010; 
struct qnode 
{ 
      int v; 
      int c; 
      qnode(int _v=0,int _c=0):v(_v),c(_c){} 
      bool operator <(const qnode &r)const 
      { 
        return c>r.c; 
      } 
}; 
struct Edge 
{ 
      int v,cost; 
      Edge(int _v=0,int _cost=0):v(_v),cost(_cost){} 
}; 
vector<Edge>E[maxn]; 
bool vis[maxn]; 
int dist[maxn]; 
void Dijkstra(int n,int start)        //点的编号从1开始 
{ 
    memset(vis,false,sizeof(vis)); 
      for(int i=1;i<=n;i++)dist[i]=INF; 
      priority_queue<qnode>que; 
      while(!que.empty())que.pop(); 
      dist[start]=0; 
      que.push(qnode(start,0)); 
      qnode tmp; 
      while(!que.empty()){
          tmp=que.top(); 
        que.pop(); 
        int u=tmp.v; 
        if(vis[u])continue; 
        vis[u]=true; 
        for(int i=0;i<E[u].size();i++){ 
              int v=E[tmp.v][i].v; 
              int cost=E[u][i].cost; 
              if(!vis[v]&&dist[v]>dist[u]+cost){ 
                dist[v]=dist[u]+cost; 
                que.push(qnode(v,dist[v])); 
              } 
        } 
      } 
} 
void addedge(int u,int v,int w) 
{
    E[u].push_back(Edge(v,w)); 
} 

【Bellman-ford算法】

• 复杂度O（V*E）
• 可以处理负边权图

//可以判断是否存在负环回路
//返回true,当且仅当图中不包含从源点可达的负权回路 
//vector<Edge>E;
//先E.clear()初始化，然后加入所有边 
const int INF=0x3f3f3f3f; 
const int maxn=550; 
int dist[maxn]; 
struct Edge 
{ 
  int u,v; 
  int cost; 
  Edge(int _u=0,int _v=0,int _cost=0):u(_u),v(_v),cost(_cost){}     //构造函数 
}; 
vector<Edge>E; 
bool bellman_ford(int start,int n)    //点的编号从1开始 
{ 
  for(int i=1;i<=n;i++)dist[i]=INF; 
  dist[start]=0; 
  for(int  i=1;i<n;i++)            //最多做n-1次 
  { 
    bool flag=false; 
    for(int j=0;j<E.size();j++) 
    { 
      int u=E[j].u; 
      int v=E[j].v; 
      int cost=E[j].cost; 
      if(dist[v]>dist[u]+cost) 
      { 
        dist[v]=dist[u]+cost; 
        flag=true; 
      } 
    } 
    if(!flag)return  true;    //没有负环回路 
  } 
  for(int j=0;j<E.size();j++) 
    if(dist[E[j].v]>dist[E[j].u]+E[j].cost) 
      return false;    //有负环回路 
  return true;        //没有负环回路 
} 

【SPFA算法】

• 复杂度O（K*E）

//这个是队列实现，有时候改成栈实现会更加快，很容易修改 
//这个复杂度是不定的 
const int maxn=1010; 
const int INF=0x3f3f3f3f; 
struct Edge 
{ 
  int v; 
  int cost; 
  Edge(int _v=0,int _cost=0):v(_v),cost(_cost){} 
}; 
vector<Edge>E[maxn]; 
void addedge(int u,int v,int w) 
{ 
  E[u].push_back(Edge(v,w)); 
} 
bool vis[maxn];                //在队列标志 
int cnt[maxn];                //每个点的入队列次数 
int dist[maxn]; 
bool SPFA(int start,int n) 
{ 
  memset(vis,false,sizeof(vis)); 
  for(int i=1;i<=n;i++)dist[i]=INF; 
  vis[start]=true; 
  dist[start]=0; 
  queue<int>que; 
  while(!que.empty())que.pop(); 
  que.push(start); 
  memset(cnt,0,sizeof(cnt)); 
  cnt[start]=1; 
  while(!que.empty()) 
  { 
    int u=que.front(); 
    que.pop(); 
    vis[u]=false; 
    for(int i=0;i<E[u].size();i++) 
    { 
      int v=E[u][i].v; 
      if(dist[v]>dist[u]+E[u][i].cost) 
      { 
        dist[v]=dist[u]+E[u][i].cost; 
        if(!vis[v]) 
        { 
          vis[v]=true; 
          que.push(v); 
          if(++cnt[v]>n)return false;         //cnt[i]为入队列次数，用来判定是否存在负环回路 
        } 
      } 
    } 
  } 
  return true; 
} 

【Floyd-Warshall算法】

• 复杂度O（n³）
• 边权非负

#include<cstdio>  
using namespace std;  
#define INF 1e9  
const int maxn=100+10;  
int n,m;                //点数,边数,点从0到n-1编号  
int dist[maxn][maxn];    //记录距离矩阵  
int path[maxn][maxn];    //path[i][j]=x表示i到j的路径上(除i外)的第一个点是x.  
void init()  
{  
    for(int i=0;i<n;i++)  
    for(int j=0;j<n;j++)  
    {  
        dist[i][j] = i==j ? 0 : INF;    //其实这里d[i][j]应该还要通过输入读数据的  
        path[i][j] = j;  
    }  
  
    //读取其他dist[i][j]的值  
}  
void floyd()  
{  
    for(int k=0;k<n;k++)  
    for(int i=0;i<n;i++)  
    for(int j=0;j<n;j++)  
    if(dist[i][k]<INF && dist[k][j]<INF )  
    {  
        if(dist[i][j]>dist[i][k]+dist[k][j])  
        {  
            dist[i][j] = dist[i][k]+dist[k][j];  
            path[i][j] = path[i][k];  
        }  
        else if(dist[i][j] == dist[i][k]+dist[k][j] &&path[i][j]>path[i][k])  
        {  
            path[i][j] = path[i][k];  //最终path中存的是字典序最小的路径  
        }  
    }  
}  
  
int main()  
{  
    //读n和m  
    init();  
    //读m条边  
    floyd();  
    //输出所求最短路径距离  
    return 0;  
}