1. 单源最短路问题 （Bellman-Ford 算法）
单源最短路是固定一个起点，求它到其他所有点的最短路问题。
记从起点 s 出发到顶点 i 的最短距离为 d[ i ]，则有等式成立：
d[ i ] = min{ d[ j ] + (从 j 到 i 的边的权值) | e = (j, i) ∈ E }
如果给定的图是一个DAG，就可以利用这条递推关系计算出 d。但是如果图中有圈，就无法这样计算。
记当前到顶点 i 的最短路长度为 d[ i ], 并设初值 d[ s ] = 0, d[ i ] = INF, 再不断使用递推式更新 d 的值， 就可以算出新的 d。只要图中不存在负圈（总长度小于0的有向环路），这样的更新操作就是有限的。结束之后 d 就是所求最短距离。
// 从顶点 from 指向顶点 to 的权值为 cost 的边 struct edge{ int from; int to; int cost; }; edge es[MAX_E]; int d[MAX_V]; //最短距离 int V, E; //求解从 s 出发到所有点的最短距离 void shortest_path(int s) { for (int i = 0; i < V; i++) d[i] = INF; d[s] = 0; while(true) { bool update = false; for (int i = 0; i < E; i++) { edge e = es[i]; if (d[e.from ] != INF && d[e.to ] > d[e.from ] + e.cost ) { d[e.to ] = d[e.from ] + e.cost; update = true; } } if (!update) break; } }
如果在图中不存在从 s 可达的负圈， 那么最短路不会经过同一顶点两次（也就是说最多通过 | V | - 1 条边），while（true） 最多执行 | V | - 1 次，因此复杂度是0（| V | * | E |）。反之，如果存在从 s 可达的负圈，那么在第| V | 次循环中也会更新 d 的值， 因此可用这个性质来检查负圈。如果一开始对所有顶点 i， 都把 d[ i ] 初始化为0，那么可以检查出所有的负圈。
// 如果返回 true 则存在负圈 bool find_negative_loop() { memset(d, 0, sizeof(d)); for (int i = 0; i < V; i++) { for (int j= 0; j < E; j++) { edge e = es[j]; if(d[e.to] > d[e.from] + e.cost) { d[e.to] = d[e.from] + e.cost; // 如果第 n 次仍然更新了，则存在负圈 if (i == V - 1) return true; } } } return false; }
2.单源最短路问题（Dijkstra 算法）
让我们来考虑一下没有负边的情况。在 Bellman-Ford算法中，如果d[ i ] 还不是最短距离的话，那么即使进行 d[ j ] = d[ i ] + (从 i 到 j 的边的权值的更新)，d[ j ]也不会变成最短距离。而且即使d[ i ] 没有变化， 每次循环也要检查一遍从 i 出发的所有边。这显然是浪费时间的。因此对算法做如下修改。
（1） 找到最短距离已经确定的顶点，从它出发更新相邻顶点的最短距离。
（2） 此后不需要再关心（1）中的最短距离已经确定的点。
那么怎么确定这个顶点？在最开始的时候，只有起点的最短距离是确定的，而在尚未使用的顶点中，距离 d[ i ] 最小的顶点就是最短距离已经确定的顶点。这是因为由于不存在负边，所以 d[ i ]不会在之后的更新中变小。
int cost[MAX_V][MAX_V]; //cost[u][v]表示边 e = （u，v）的权值，不存在是为INF int d[MAX_V]; //顶点s出发的最短距离 bool used[MAX_V]; //已经使用过的图 int V; //求从起点s出发到各顶点的最短距离 void dijkstra(int s) { fill(d, d + V, INF); fill(used, used + V, false); d[s] = 0; while(true) { int v = -1; //从尚未使用的顶点中选择一个距离最小的顶点 for (int u = 0; u < V; u++) if (!used[u] && (v == -1 || d[u] < d[v])) v = u; if (v == -1) break; used[v] = true; for (int u = 0; u < V; u++) d[u] = min(d[u], d[v] + cost[v][u]); } }
使用邻接矩阵实现的话复杂度为0（| V |2）.使用邻接表的话，更新最短距离只需要访问每条边一次即可，因此这部分的复杂度为0（| E |）。但每次都要枚举所有的顶点来查找下一个使用的顶点，因此最终复杂度仍为0（| V |2）。需要优化的是数值的插入（更新）和取出，使用堆可以解决。把每个顶点当前的最短距离用堆来维护。而每次从堆中取出的最小值就是下一次要使用的顶点。这样堆中的元素共有0（| V |）个，更新和取出数值的操作有0（| E |）次，因此整个算法复杂度为0（| E | log | V |）。
struct edge { int to; int cost; }; typedef pair<int, int> P; //first 是最短距离， second是顶点的编号 int V; vector<edge> G[MAX_V]; int d[MAX_V]; void dijkstra(int s) { //通过指定greater<P> 参数，堆按照first从小到大排序 priority_queue<P, vector<P>, greater<P> > q; fill(d, d + V, INF); q.push(P(0, s)); while (!q.empty()) { P p = q.top(); q.pop(); int v = p.second; if (d[v] < q.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; q.push(P(d[e.to], e.to)); } } } }
相对于Bell-Ford的0（| V | | E |）的复杂度，Dijkstra算法的复杂度是0（| E | log | V |）更高效，但是在图中存在负边的情况下，Dijkstra就无法正确求解，还是需要用Bell-Ford算法。
3.任意两点间的最短路问题（Floyed-Warshall 算法）
原文：https://www.cnblogs.com/astonc/p/10739103.html