最短路径
1.从一个源点到其它各点的最短路径
单源点的最短路径问题：给定带权有向图 G＝（V，E）和源点 v∈V，求从 v 到 G 中其余各顶点的最短路径。
（1）求从源点到其余各点的最短路径的算法的基本思想：依最短路径的长度递增的次序求得各条路径。
①假设图中所示为从源点到其余各点之间的最短路径，则在这些路径中，必然存在一条长度最短者。其中，从源点到顶点 v 的最短路径是所有最短路径中长度最短者。
②路径长度最短的最短路径的特点：
在这条路径上，必定只含一条弧，并且这条弧的权值最小。
③下一条路径长度次短的最短路径的特点：
它只可能有两种情况：或者是直接从源点到该点(只含一条弧)；或者是，从源点经过顶点v1，再到达该顶点(由两条弧组成)。
④再下一条路径长度次短的最短路径的特点:
它可能有三种情况：或者是，直接从源点到该点(只含一条弧)；或者是，从源点经过顶点v1，再到达该顶点(由两条弧组成)；或是，从源点经过顶点 v2，再到达该顶点。
⑤其余最短路径的特点：
它或者是直接从源点到该点(只含一条弧)；或者是，从源点经过已求得最短路径的顶点，再到达该顶点。
（2）迪杰斯特拉（Dijkstra）算法
迪杰斯特拉提出的一个按路径长度递增的次序产生最短路径的算法。
该算法的基本思想是：设置两个顶点的集合 S 和 T＝V－S，集合 S 中存放已找到最短路径的顶点，集合 T 存放当前还未找到最短路径的顶点。初始状态时，集合 S 中只包含源点 v 0 ，然后不断从集合 T 中选取到顶点 v 0 路径长度最短的顶点 u 加入到集合 S 中，集合 S 每加入一个新的顶点 u，都要修改顶点 v 0 到集合 T 中剩余顶点的最短路径长度值，集合 T 中各顶点新的最短路径长度值为原来的最短路径长度值与顶点 u 的最短路径长度值加上 u 到该顶点的路径长度值中的较小值。此过程不断重复，直到集合 T 的顶点全部加入到 S 中为止。
Dijkstra 算法的正确性可以用反证法加以证明。假设下一条最短路径的终点为 x，那么，该路径必然或者是弧（v 0 ，x），或者是中间只经过集合 S 中的顶点而到达顶点 x 的路径。因为假若此路径上除 x 之外有一个或一个以上的顶点不在集合 S 中，那么必然存在另外的终点不在 S 中而路径长度比此路径还短的路径，这与我们按路径长度递增的顺序产生最短路径的
前提相矛盾，所以此假设不成立。
下面介绍 Dijkstra 算法的实现。
首先，引进一个辅助向量 D，它的每个分量 D[i] 表示当前所找到的从始点 v 到每个终点v i 的最短路径的长度。它的初态为：若从 v 到 v i 有弧，则 D[i]为弧上的权值；否则置 D[i]为∞。显然，长度为：
D[j]=Min{D[i]| v i ∈V}的路径就是从 v 出发的长度最短的一条最短路径。此路径为（v ,vj）。
那么，下一条长度次短的最短是哪一条呢？假设该次短路径的终点是 v k ，则可想而知，这条路径或者是（v, v k ），或者是（v, v j , v k ）。它的长度或者是从 v 到 v k 的弧上的权值，或者是 D[j]和从 v j 到 v k 的弧上的权值之和。
依据前面介绍的算法思想，在一般情况下，下一条长度次短的最短路径的长度必是：D[j]=Min{D[i]| vi∈V-S}
其中，D[i] 或者弧（v, v i ）上的权值，或者是 D[k]( v k ∈S 和弧（v k , v i ）上的权值之和。
根据以上分析，可以得到如下描述的算法：
①假设用带权的邻接矩阵 edges 来表示带权有向图，edges[i][j] 表示弧〈v i , v j 〉上的权值 。若〈v i , v j 〉不存在，则置 edges[i][j]为∞（在计算机上可用允许的最大值代替）。S 为已找到从v 出发的最短路径的终点的集合，它的初始状态为空集。那么，从 v 出发到图上其余各顶点（终点）v i 可能达到最短路径长度的初值为：
D[i]= edges[Locate Vex(G,v)][i] vi∈V
②选择 v j ，使得
D[j]=Min{D[i]| vi∈V-S}
v j 就是当前求得的一条从 v 出发的最短路径的终点。令S＝S∪{j}
③修改从 v 出发到集合 V-S 上任一顶点 v k 可达的最短路径长度。如果D[j]+ edges[j][k]<D[k]
则修改 D[k]为D[k]=D[j]+ edges[j][k]
④重复操作②、③共 n-1 次。由此求得从 v 到图上其余各顶点的最短路径是依路径长度递增的序列。
Dijkstra 算法的时间复杂度为 O(n^2 )。
2.每一对顶点之间的最短路径
解决这个问题的一个办法是：每次以一个顶点为源点，重复招待迪杰斯特拉算法 n 次。这样，便可求得每一结顶点的最短路径。总的执行时间为 O(n^3 )。
这里要介绍由弗洛伊德(Floyd)提出的另一个算法。这个算法的时间复杂度也是 O(n ^3 ),但形式上简单些。
弗洛伊德算法仍从图的带权邻接矩阵 cost 出发，其基本思想是：
假设求从顶点v i 到v j 的最短路径。如果从v i 到v j 有弧，则从v i 到v j 存在一条长度为arcs[i][j]的路径，该路径不一定是最短路径，尚需进行 n 次试探。首先考虑路径（v i , v 0 , v j ）是否存在（即判别弧（v i , v 0 ）和(v 0 , v j )是否存在）。如果存在，则比较（v i , v j ）和（v i , v 0 , v j ）的路径长度取长度较短者为从 v i 到 v j 的中间顶点的序号不大于 0 的最短路径。假如在路径上再增加一个顶点 v 1 ，也就是说，如果 （v i , …, v 1 ）和（v 1 , …, v j ）分别是当前找到的中间顶点的序号不大于 0 的最短路径，那么（v i , …, v 1 , … , v j ）就有可能是从 v i 到 v j 的中间顶点的序号不大于1 的最短路径。将它和已经得到的从 v i 到 v j 中间顶点序号不大于 0 的最短路径相比较，从中选出中间顶点的序号不大于 1 的最短路径之后，再增加一个顶点 v 2 ，继续进行试探。依次类
推。在一般情况下，若（v i , …, v k ）和（v k , …, v j ）分别是从 v i 到 v k 和从 v k 到 v j 的中间顶点的序号不大于 k-1 的最短路径，则将（v i , …, v k , …, v j ）和已经得到的从 v i 到 v j 且中间顶点序号不大于 k-1 的最短路径相比较，其长度较短者便是从 v i 到 v j 的中间顶点的序号不大于 k 的最短路径。这样，在经过 n 次比较后，最后求得的必是从 v i 到 v j 的最短路径。按此方法，可以同时求得各对顶点间的最短路径。
现定义一个 n 阶方阵序列,D (-1) ，D (0) ，D (1) ，…，D (k) ，D (n-1)
其中
D (-1) [i][j]=edges[i][j]
D ( k) [i][j]=Min{D ( k-1) [i][j], D ( k-1) [i][k]+D ( k-1) [k][j]} 0≦k≦n-1
从上述计算公式可见，D (1) [i][j]是从v i 到v j 的中间顶点的序号不大于1的最短路径的长度；
D ( k) [i][j] 是从 v i 到 v j 的中间顶点的个数不大于 k 的最短路径的长度；D ( n-1) [i][j] 就是从 v i 到v j 的最短路径的长度。