https://blog.csdn.net/mmy1996/article/details/52225893 算法比较
https://blog.csdn.net/yuewenyao/article/details/81023035 时间复杂度之间的比较
四种最短路求法;
时间复杂度：
Floyd, 堆优化：Dijkstra, Bellman-Ford, Spfa
|
O（N³） |
O（(m+n)logN） |
O（MN） |
最坏也是O（NM） |
Dijkstra: 迪杰斯特拉 ：O（(m+n)logN）
最短路径中不能包含负权回路，因为每次经过负权回路，路径的权值会减少
参考题目：HDU - 1874 畅通工程续 （dijkstra模板） POJ - 3268 Silver Cow Party （dijkstra） （向前星存储）
POJ - 2387 Til the Cows Come Home（dijkstra）（vector邻接表存储）
POJ - 1502 MPI Maelstrom （dijkstra） 邻接矩阵(数组)
（堆优化/链式向前星）模板：
//n个点，m条边
#include<bits/stdc++.h> using namespace std; #define maxn 10005 #define maxm 500005 #define INF 0x3f3f3f3fstruct Edge { int u,v,w,next; }edge[maxm]; int head[maxm],cnt,n,m,s,vis[maxn],dis[maxn]; #define P pair<long long,int> priority_queue<P,vector<P>,greater<P> >q; //把最小的元素放在队首的优先队列 inline void add(int u,int v,int w) { edge[++cnt].u=u; //这句话对于此题不需要，但在缩点之类的问题还是有用的 edge[cnt].v=v; edge[cnt].w=w; edge[cnt].next=head[u]; //存储该店的下一条边 head[u]=cnt; //更新目前该点的最后一条边（就是这一条边） } //s为起点 void dijkstra(int s) { for(int i=1;i<=n;i++) { dis[i]=INF; } dis[s]=0; //赋初值 q.push(make_pair(0,s)); while(!q.empty()) //堆为空即为所有点都更新 { int x=q.top().second; q.pop(); //记录堆顶并将其弹出 if(!vis[x]) //没有遍历过才需要遍历 { vis[x]=1; for(int i=head[x];i;i=edge[i].next) //搜索堆顶所有连边 { int v=edge[i].v; dis[v]=min(dis[v],dis[x]+edge[i].w); //松弛操作 q.push(make_pair(dis[v],v)); } } } }
Bellman – Ford 算法
https://www.cnblogs.com/fzl194/p/8728529.html
适用前提：
没有负环（或称为负权值回路），因为有负环的话距离为负无穷如果迭代n-1次后，再次迭代，如果此时还有dist会更新，说明存在负环。
无负环的时候，迭代更新次数最多为n-1次，所以设置一个更新变量可以在不更新的时候直接跳出循环Bellman-Ford算法还能用来求最长路或者判断正环。
思路是dist数组含义是从原点出发到其他每个顶点的最长路径的长度：初始时，各个顶点dist为0，在从distk-1[u]递推到distk[u]的时候，Bellman-Ford算法的本质是对每条边<u, v>进行判断：设边<u, v>的权值为w(u, v)，如果边<u, v>的引入会使得distk-1[v]的值再增加，就要修改distk-1[v]，即：如果distk-1[u] + w(u, v) > distk-1[v],，那么distk[v] = distk-1[u] + w(u, v)
参考题目：POJ - 2240 Arbitrage (bellman-ford，正权回路问题)
Floyd 弗洛伊德 （简单粗暴）
https://www.cnblogs.com/wangyuliang/p/9216365.html
Floyd-Warshall算法的原理是动态规划。
设Di,j,k为从i到j的只以(1..k)集合中的节点为中间节点的最短路径的长度。
若最短路径经过点k，则Di,j,k = Di,k,k − 1 + Dk,j,k − 1；
若最短路径不经过点k，则Di,j,k = Di,j,k − 1。
因此，Di,j,k = min(Di,k,k − 1 + Dk,j,k − 1,Di,j,k − 1)。
参考题目： POJ - 3259 Wormholes （floyd) floyd判断负环回路
POJ - 3660 Cow Contest （floyd,传递闭包）传递闭包问题
void floyd(){ for(k = 1; k <= n; k++){ for(i = 1; i <= n; i++){ for(j = 1; j < i; j++){ if(!g[i][k]||!g[k][j]) continue; if(!g[i][j]|| g[i][k] + g[k][j] < g[i][j]) g[i][j] = g[j][i] = g[i][k] + g[k][j]; } } } }
Spfa （Bellman-ford队列优化）
SPFA 算法是 Bellman-Ford算法 的队列优化算法的别称，通常用于求含负权边的单源最短路径，以及判负权环。
SPFA 最坏情况下复杂度和朴素 Bellman-Ford 相同，为 O(VE)。
单源最短路
求带权有向图上一个源点到其他点的最短路径距离
如果没有非负边权，我们自然可以想到dijkstra。但是如果有负边权呢？这时候就要用SPFA算法求解。
用dis数组记录源点到有向图上任意一点距离，其中源点到自身距离为0，到其他点距离为INF。将源点入队，并重复以下步骤：
(1)队首x出队
(2)遍历所有以队首为起点的有向边(x,i)，若dis[x]+w(x,i)<dis[i]，则更新dis[i]
(3)如果点i不在队列中，则i入队
(4)若队列为空，跳出循环；否则执行1
看作bfs来理解
由于SPFA的算法复杂度是 O(NM) ，可以构造出卡SPFA的数据，让SPFA超时。但是负权图我们只能用这个来做
#include<bits/stdc++.h>
using namespace std; const int maxm = 1e6+5; const int maxn = 1e3+5; const int inf = 0xffffff; struct edge{ int from; int to; int w; int next; }e[maxm]; int head[maxn]; int vis[maxn]; int dist[maxn]; int n,m,top; void add(int u,int v,int w){ e[top].from = u; e[top].to = v; e[top].w = w; e[top].next = head[u]; head[u] = top++; } void spfa(int s){ queue<int> q; for(int i = 1; i <= n ; i++) dist[i] = inf; memset(vis,false,sizeof(vis)); q.push(s); dist[s] = 0; while(!q.empty()){ int u = q.front() ; q.pop(); vis[u] = false ; for(int i = head[u] ; ~i ; i = e[i].next){ int v = e[i].to; if(dist[v] > dist[u] + e[i].w){ dist[v] = dist[u] + e[i].w; if(!vis[v]){ vis[v] = true; q.push(v); } } } } }
原文：https://www.cnblogs.com/Tianwell/p/11357280.html