图的五种求最短路径算法（Dijkstra、堆优化Dijstra、Bellmon-Ford、SPFA、Floyd-Warshall）

图的五种求最短路径算法（Dijkstra、堆优化Dijstra、Bellmon-Ford、SPFA、Floyd-Warshall）

V代表顶点个数 E代表边数

1. Dijkstra算法 适合正权(不含负权)稠密图 时间复杂度为O(V^2) 只与顶点个数有关 慎用邻接矩阵 需要考虑初始化为INF 有向图和无向图 重边 和 自环

   //Acwing 849
   #include<iostream>
   using namespace std;
   const int V=1e3;//最大顶点个数
   const int INF = 1e9;
   int adj[V][V]; //邻接矩阵 在存入数据的时候记得考虑初始化，以及无向图和有向图处理方式不同   还要考虑 重边和自环的问题
   bool used[V]; //判断是否使用过
   int d[V]; //最短距离
   int n,m,ts,te; //无向图 给你n个顶点 m条边 求从ts到特最短路径
   int Dijkstra();
   
   int main() {
   	scanf("%d%d%d%d",&n,&m,&ts,&te);
       fill(adj[0],adj[0]+V*V,INF);  //邻接矩阵一定要初始化为INF
       for(int i=0;i<m;i++) {
           int a,b,w;
           scanf("%d%d%d",&a,&b,&w);
           adj[a][b] = adj[b][a] = w;
       }
       int t=Dijkstra();
       if(t==INF) printf("impossible"); //此路不通
       else printf("%d",t); //输出最短路径
   }
   
   int Dijkstra() {
       fill(used,used+V,false); //初始化
       fill(d,d+V,INF);
       d[ts]=0;   //起点最短路径必须设为0
       while(1) {
           int v=-1;
           for(int i=1;i<=n;i++) {  //寻找一个没有使用过的距离起点最近的点
               if(!used[i]&&(v==-1||d[v]>d[i])) v=i;
           }
           if(v==-1) break; //全部都使用过了
           used[v]=true;
           for(int j=1;j<=n;j++) { //更新最短路径
               d[j] = min(d[j],d[v]+adj[v][j]);
           }
       }
       return d[te];
   }
   

2. 堆优化Dijkstra算法 适合正权稀疏图 时间复杂度O(E logV )

   //Acwing850
   //使用 优先队列 d[V] pair<int,int> 
   #include<iostream>
   #include<queue>
   using namespace std;
   const int INF=1e9,V=1e6;
   int d[V];
   struct edge {int to,cost;};
   vector<edge> G[V];
   typedef pair<int,int> P;
   int n,m;
   int quickDij();
   
   int main() {
   	scanf("%d%d",&n,&m);
       for(int i=1;i<=m;i++) {
           int a,b,w;
           scanf("%d%d%d",&a,&b,&w);
           edge e={b,w}
           G[a].push_back(e);
       }
       int t=quickDij();
       if(t==INF) printf("-1");
       else printf("%d",t);
   }
   
   int quickDij() {
       priority_queue<P,vector<P>,greater<P>> que; //p.first存的是最短距离 p.second存的是顶点
       fill(d,d+V,INF);
       d[1]=0;
       que.push(P(0,1));
       while(que.size()) {
           P p=que.top();
           que.pop();
           int v=p.second;
           if(d[v]<p.first) continue; //冗余了
           for(int i=0;i<G[v].size();i++) {
               edge e=G[v][i];
               if(d[e.to] > d[v] + e.cost) {
                   d[e.to] = d[v]+e.cost;
                   que.push(P(d[e.to],e.to));
               }
           }
       }
       return d[n];
   }
   

3. Bellmon-Ford算法 适合有负权的图 边数限制的最短路径问题只能用它来求解 时间复杂度 O(V*E)

   //Acwing 853
   //n个顶点让你求从1到n边数不超过k的最短路径
   #include<iostream>
   #include<cstring>
   using namespace std;
   const int INF=1e9,V=600,E=1e6;
   int d[V],backup[V]; //backup用于保留上一次d迭代结果 防止发生串联反应 无法控制边的数量
   int Bellmon();
   int n,m,k;
   struct edge {
       int a,b,w;
   };
   edge es[E]; //存放给的所有边 尽量大
   
   int main() {
       scanf("%d%d%d",&n,&m,&k);
       for(int i=0;i<m;i++) {
           int a,b,w;
           scanf("%d%d%d",&a,&b,&w);
           es[i]={a,b,w};
       }
       int t=Bellmon();
       if(t==INF) printf("impossible");  //或者这句话改为t>INF/2  就可以去掉 下面的if(backup[e.a]!=INF)  就代表没有通路 因为存在负权 有的影响INF  
       else printf("%d",t);
   }
   
   int Bellmon() {
       fill(d,d+V,INF);
       d[1]=0;
       for(int i=0;i<k;i++){
           memcpy(backup,d,sizeof d);
           for(int j=0;j<m;j++) {
               edge e=es[j];
               if(backup[e.a]!=INF) //防止存在负权 对那些明明无法联通的点却改变INF
               	d[e.b] =min(d[e.b],backup[e.a]+e.w); //用上一次迭代结果更新 防止发生串联
           }
       }
       return d[n];
   }
   

4. SPFA 适合绝大多数情况 但可能被卡样例 存在负圈无法求解 时间复杂度最好是 O(E)

   最坏 O(V*E)

   //Acwing 851
   #include<iostream>
   #include<queue>
   using namespace std;
   const int V=1.5e5,INF=1e9;
   int d[V];
   int nums[V]; //加上这个可以判断负圈
   struct edge {
       int to,cost;
   };
   vector<edge> G[V];
   int SPFA();
   int n,m;
   bool qj[V];
   
   int main() {
       scanf("%d%d",&n,&m);
       for(int i=0;i<m;i++) {
           int a,b,w;
           scanf("%d%d%d",&a,&b,&w);
           edge e={b,w};
           G[a].push_back(e);
       }
       int t=SPFA();
       if(t>INF/2) printf("impossible");
       else printf("%d",t);
   }
   
   int SPFA() {
       fill(qj,qj+V,false);
       fill(d,d+V,INF);
       fill(nums,nums+V,0);
       d[1]=0;
       queue<int> q;
       q.push(1);
       qj[1]=true;
       nums[1]++;
       while(q.size()) {
           int p=q.front();
           q.pop();
           qj[p]=false;
           for(int i=0;i<G[p].size();i++) {
               edge e = G[p][i];
               if(d[e.to]>d[p]+e.cost) {
                   d[e.to] = d[p]+e.cost;
                   if(!qj[e.to]){
                       q.push(e.to);
                       qj[e.to]=true;
                   }
                   nums[e.to]++;
                   if(nums[e.to]>n) return -1; //一个顶点入队超过n次就是图中存在负圈
               }
           }
       }
       return d[n];
   }
   

5. Floyd-Warshall 多源路径求解 O(V^3)

   int d[MAX_V][MAX_V];  //d是邻接矩阵  循环结束就是i-->j最短路径 V 是顶点个数
   for(int k=0;k<V;k++)
       for(int i=0;i<V;i++)
           for(int j=0;j<v;j++)
               d[i][j] = d[i][k] + d[k][j];
   

本文地址：https://blog.csdn.net/Y810614/article/details/110143980