1. Dijstra是基于贪心思想地算法，具体做法是从源点开始，每次找出还没有被最短路点集收录且离源点最近的点然后对其相邻的点进行松弛，进行n次迭代以后即可得到最短路。具体实现为：
int Dijstra( int n ){
memset( dist , 0x3f , sizeof ( dist ) ) ;
dist [S] = 0;
for( int i = 0 ; i < n ; i++ ) {
int t = -1;
for( int i=1 ; i <= n ; i++ ) if ( ! st[i] && ( t == -1 || dist[i] < dist[t] ) ) t = i;
st [ t ] = true;
for ( int j = 1 ; j <= n ; j++) {
dist [ j ] = min ( dist [ j ] ,dist [ t ] + g [ t ] [ j ] );
}
}
if ( dist[n] == 0x3f3f3f3f ) return -1;
return dist[n];
}
其中 S 为源点，dist [ i ] 表示源点到 i 号点的最短距离，初始化 dist [S] = 0，其他距离为正无穷，st [ i ]表示 i 号点是否被最短路集合收录。
Dijstra也有堆优化的方法，即把松弛操作用优先队列队列优化,即：
1. dist的源点的距离初始化为零，其他点初始化成无穷大。
2. 将一号点放入堆中。
3. 不断循环，直到堆空。每一次循环中执行的操作为：
弹出堆顶（与朴素版diijkstra找到S外距离最短的点相同，并标记该点的最短路径已确定）。用该点更新临界点的距离，若更新成功就加入到堆中。
具体实现略，这个很好写。
2. SPFA，号称最短路最快算法 ( Shortest Path Fastest Algorithm ) ,是Bellman_Ford算法的队列优化，因此先看Bellman_Ford算法。它的思想非常暴力：进行 n 次迭代，每次遍历所有的边并对该边的终点进行松弛操作，最后得到最短路。即：
for n次
for 所有边 a,b,w (松弛操作)
dist [b] = min ( dist [b] , back [a] + w )
这里要注意的是 back 数组，它是上一次迭代后 dist 数组的备份。这是因为该算法最外层第k次迭代的意义是：从源点经过不超过k条边的最短路。如果直接使用 dist 数组进行松弛可能会出现边的串联现象。
不难看出 Bellman_Ford 的弊端：每次都要遍历所有的边，但不是每条边都需要松弛。对于这一步操作进行队列优化就是SPFA。即：
while queue 不为空
(1) t <– 队头
queue.pop()
(2)用 t 更新所有出边 t –> b，权值为w
queue <– b (若该点被更新过，则拿该点更新其他点)
具体实现为：
bool SPFA() {
memset( dist , 0x3f , sizeof(dist) );
dist [1] = 0;
queue < int > qe;
qe.push (1);
st [1] = true;//注意这里的 st 代表是否在队列中
while( ! qe.empty() ) {
int t = qe.front();
qe.pop();
st [ t ] = false;
for( int i = h[ t ] ; i != -1 ; i = ne [ i ] ) {
int j = e [ i ] ,v = w [ i ] ;
if ( dist [ j ] > dist [ t ] + v ){
dist [ j ] = dist [ t ] + v ;
if ( ! st [ j ] ) { // 以免重复加入节点
st [ j ] = true;
qe.push(j);
}
}
}
}
if ( dist [ n ] > 0x3f3f3f3f / 2 ) return false;
return true;
}
3. Floyd用于求多源最短路问题，是基于动态规划的算法。先用f [ i , j, k ] 表示从i走到j的路径上除 i 和 j 点外只经过1到 k 的点的所有路径的最短距离，则其状态转移方程为：
f [ i , j, k ] = min ( f [ i , j , k - 1] , f [ i , k , k - 1 ] + f [ k , j , k - 1 ] )
由此公式可得f [ k ] [ i ] [ k ] = f [ k-1 ] [ i ] [ k ] 、f [ k ] [ k ] [ j ] = f [ k-1 ] [ k ] [ j ] ，因为k不可能是（i, k）或者（k, j）的中间节点
所以 f [ k ] [ i ] [ j ] = min ( f [ k−1 ] [ i ] [ j ], f [ k ] [ i ] [ k ] + f [ k ] [ k ] [ j ] )
所以去掉最外层循环，因此第三层状态可以压缩：
f [ i , j ] = min ( f [ i , j ] , f [ i , k ] + f [ k , j ] ）
具体实现：
void floyd() {
for ( int k = 1 ; k <= n ; k++ )
for ( int i = 1 ; i <= n ; i++ )
for ( int j = 1 ; j <= n ; j++)
dist [ i ] [ j ] = min ( dist [ i ] [ j ] , dist [ i ] [ k ] + dist [ k ] [ j ] ) ;
}
dist 初始化为图的邻接矩阵 g。
总结一下，关于算法复杂度(n为点数，m为边数)：
Dijstra要求所有权边都是正数:
Dijstra : O(n^2) 适用于稠密图
堆优化Dijstra : O(m*logn) 适用于稀疏图
如果存在负权边则用SPFA:
Bellman_Ford : O(n*m) 有边数限制时最短路的唯一算法
SPFA : 一般为 O(m)，最坏情况下为 O(n*m)，与朴素 Bellman_Ford 一样。
SPFA正负权图都可以用，并且正权图一般情况下都快于Dijstra，但鉴于现在正权图上随手卡SPFA已是业界常识（比如网格图加菊花链），Dijstra还是更稳的。关于SPFA，它死了。。。。
多源汇最短路:
Floyd : O(n^3) 多源最短路
