相关概念：
有向图、无向图：有向图的边是双行道，无向图的边是单行道。在处理无向图时，可以把一条无向边看做方向相反的两条有向边。
圈 cycle / 回路 circuit：在相同顶点上开始并结束且长度大于0的通路。
环 loop：起点与终点重合的边。
负圈：含有负权边的圈。
| 问题类型？ | 是否兼容负圈？ | 时间复杂度？ | |
| Bellman-Ford | 单源 | √ | O(V·E) |
| Dijkstra | 单源 | × | O(E·logV) |
| Floyd-Warshall | 任意点对 | √ | O(V3) |
1. Bellman-Ford 算法（单源） O(VE)
设d[]存放最短路径，对于每条边(from, to)，d[to] = d[from] + cost 一定成立。
由于边在es[]中存储顺序的关系，可能出现计算到 d[to] 时 d[from] 还没出现的情况，此时d[to] 的值会继续保持INF，等到下一次循环再被更新。
当图中存在V个点时，从起点s出发共有V-1条路径，因此外层循环最多执行V-1次就能消除d[]中所有INF，并得到结果。如果图中存在负圈，最短路径会不断减小，外层循环执行次数就会超过V-1，因此只需检查更新次数是否达到V就能判断是否存在负圈。
1 struct edge{int from,to,cost;}; 2 3 edge es[MAX_E]; 4 int d[MAX_V]; //shortest paths 5 int V,E; //number of vertices and edges 6 7 bool bellman_ford(int s) 8 { 9 for(int i=0;i d[e.from]+e.cost){18 d[e.to]=d[e.from]+e.cost;19 update=true;20 }21 }22 if(!update)23 break;24 if(n==V-1) //negative loops exists25 return true;26 }27 return false;28 }
2.Dijkstra 算法（单源、无负圈）O(E·logV)
该算法的核心在于从已经确定最短路径的点出发，寻找相邻点的最短路径。
令d[s]=0，先更新s所有邻居的sp，入队，再从s所有邻居开始，更新它们的邻居的sp，以此类推……
借助升序优先队列，优先执行sp值小的点，可以避免内层for循环被不断执行，有效减小时间复杂度。
1 struct edge{int to,cost;}; 2 typedef pair P; //first:sp second:termination 3 4 int V,E; 5 vector G[MAX_V]; //adjcent list 6 int d[MAX_V]; 7 8 void dijkstra(int s) 9 {10 priority_queue ,greater
> que; //#include
11 fill(d,d+V+1,INF);12 d[s]=0;13 que.push(P(0,s));14 15 while(!que.empty()){16 P p=que.top(); que.pop();17 int v=p.second;18 if(d[v] d[v]+e.cost){22 d[e.to]=d[v]+e.cost;23 que.push(P(d[e.to],e.to)); //newly updated sp may change the sp of its neighbours24 }25 }26 }27 } 计算最短路径条数的方法：
维护数组 int cnt[MAX_V] 并初始化为 cnt[]=0; cnt[s]=1;
if ( d[e.to] > d[v]+e.cost ) cnt[e.to]=cnt[v]
else if ( d[e.to] == d[v]+e.cost ) cnt[e.to]+=cnt[v]
3.Floyd-Warshall 算法（任意点间） O(V3)
对于每个点对(i, j ) ，枚举中间点 k。i 到 j 的最短路径取经过中间点 k 和不经过中间点 k 两种情况的结果的最小值。
需要初始化：d[i][i]=0，不存在=INF
int d[MAX_V][MAX_V]; //weight of edgesint V,E;void floyd_warshall(){ for(int k=0;k
参考《挑战程序设计竞赛》（第二版），99-104；离散数学及其应用（中文第七版），595-612