副标题#e#
在这个问题中，给出有向图G，它的每条边都有一个非负的长度（淹灭） a [i ][ j ]，路径的长度即为此路径所颠末的边的长度之和。对付给定的源极点s，需找出从它到图中其他任意极点（称为目标）的最短路径。图13-10a 给出了一个具有五个极点的有向图，各边上的数即为长度。假设源极点s 为1，从极点1出发的最短路径按路径长度顺序列在图13-10b 中，每条路径前面的数字为路径的长度。
操作E. Dijkstra发现的贪婪算法可以办理最短路径问题，它通过度步要领求出最短路径。每一步发生一个达到新的目标极点的最短路径。下一步所能到达的目标极点通过如下贪婪准则选取：在还未发生最短路径的极点中，选择路径长度最短的目标极点。也就是说， D i j k s t r a的要领按路径长度顺序发生最短路径。
首先最初发生从s 到它自身的路径，这条路径没有边，其长度为0。在贪婪算法的每一步中，发生下一个最短路径。一种要领是在今朝已发生的最短路径中插手一条可行的最短的边，功效发生的新路径是原先发生的最短路径加上一条边。这种计策并不老是起浸染。另一种要领是在今朝发生的每一条最短路径中，思量插手一条最短的边，再从所有这些边中先选择最短的，这种计策等于D i j k s t r a算法。
可以验证按长度顺序发生最短路径时，下一条最短路径老是由一条已发生的最短路径加上一条边形成。实际上，下一条最短路径老是由已发生的最短路径再扩充一条最短的边获得的，且这条路径所达到的极点其最短路径还未发生。譬喻在图1 3 – 1 0中，b 中第二条路径是第一条路径扩充一条边形成的；第三条路径则是第二条路径扩充一条边；第四条路径是第一条路径扩充一条边；第五条路径是第三条路径扩充一条边。
通过上述调查可用一种轻便的要领来存储最短路径。可以操作数组p，p [ i ]给出从s 达到i的路径中极点i 前面的谁人极点。在本例中p [ 1 : 5 ] = [ 0 , 1 , 1 , 3 , 4 ]。从s 到极点i 的路径可反向建设。从i 出发按p[i],p[p[i]],p[p[p[i]]], .的顺序，直到达到极点s 或0。在本例中，假如从i = 5开始，则极点序列为p[i]=4, p[4]=3, p[3]=1=s，因此路径为1 , 3 , 4 , 5。
为能利便地按长度递增的顺序发生最短路径，界说d [ i ]为在已发生的最短路径中插手一条最短边的长度，从而使得扩充的路径达到极点i。最初，仅有从s 到s 的一条长度为0的路径，这时对付每个极点i，d [ i ]便是a [ s ] [ i ]（a 是有向图的长度连接矩阵）。为发生下一条路径，需要选择还未发生最短路径的下一个节点，在这些节点中d值最小的即为下一条路径的终点。当得到一条新的最短路径后，由于新的最短路径大概会发生更小的d值，因此有些极点的d值大概会产生变革。
综上所述，可以获得图1 3 – 11所示的伪代码， 1) 将与s 连接的所有极点的p 初始化为s，这个初始化用于记录当前可用的最好信息。也就是说，从s 到i 的最短路径，等于由s到它自身那条路径再扩充一条边获得。当找到更短的路径时， p [ i ]值将被更新。若发生了下一条最短路径，需要按照路径的扩充边来更新d 的值。
1) 初始化d[i ] =a[s] [i ]（1≤i≤n），
对付连接于s的所有极点i，置p[i ] =s, 对付其余的极点置p[i ] = 0；
对付p[i]≠0的所有极点成立L表。
2) 若L为空，终止，不然转至3 )。
3) 从L中删除d值最小的极点。
4) 对付与i 连接的所有还未达到的极点j，更新d[ j ]值为m i n{d[ j ], d[i ] +a[i ][ j ] }；若d[ j ]产生了变革且j 还未
在L中，则置p[ j ] = 1，并将j 插手L，转至2。
图1 – 11 最短路径算法的描写
#p#副标题#e#
1. 数据布局的选择
我们需要为未达到的极点列表L选择一个数据布局。从L中可以选出d 值最小的极点。假如L用最小堆（见9 . 3节）来维护，则这种选取可在对数时间内完成。由于3) 的执行次数为O ( n )，所以所需时间为O ( n l o g n )。由于扩充一条边发生新的最短路径时，大概使未达到的极点发生更小的d 值，所以在4) 中大概需要改变一些d 值。固然算法中的减操纵并不是尺度的最小堆操纵，但它能在对数时间内完成。由于执行减操纵的总次数为： O(有向图中的边数)= O ( n2 )，因此执行减操纵的总时间为O ( n2 l o g n )。
若L用无序的链表来维护，则3) 与4) 耗费的时间为O ( n2 )，3) 的每次执行需O(|L | ) =O( n )的时间，每次减操纵需( 1 )的时间（需要减去d[j] 的值，但链表不消改变）。操作无序链表将图1 – 11的伪代码细化为措施1 3 – 5，个中利用了C h a i n (见措施3 – 8 )和C h a i n I t e r a t o r类（见措施3 – 1 8）。
措施13-5 最短路径措施
#p#分页标题#e#
template
void AdjacencyWDigraph::ShortestPaths(int s, T d[], int p[])
{// 寻找从极点s出发的最短路径, 在d中返回最短间隔
// 在p中返回前继极点
if (s < 1 || s > n) throw OutOfBounds();
Chain L; // 路径可达到极点的列表
ChainIterator I;
// 初始化d, p, L
for (int i = 1; i <= n; i++){
d[i] = a[s][i];
if (d[i] == NoEdge) p[i] = 0;
else {p[i] = s;
L . I n s e r t ( 0 , i ) ; }
}
// 更新d, p
while (!L.IsEmpty()) {// 寻找具有最小d的极点v
int *v = I.Initialize(L);
int *w = I.Next();
while (w) {
if (d[*w] < d[*v]) v = w;
w = I.Next();}
// 从L中删除通向极点v的下一最短路径并更新d
int i = *v;
L . D e l e t e ( * v ) ;
for (int j = 1; j <= n; j++) {
if (a[i][j] != NoEdge && (!p[j] ||
d[j] > d[i] + a[i][j])) {
// 减小d [ j ]
d[j] = d[i] + a[i][j];
// 将j插手L
if (!p[j]) L.Insert(0,j);
p[j] = i;}
}
}
}
若N o E d g e足够大，使得没有最短路径的长度大于或便是N o E d g e，则最后一个for 轮回的i f条件可简化为：if (d[j] > d[i] + a[i][j])) NoEdge 的值应在能使d[j]+a[i][j] 不会发生溢出的范畴内。
2. 巨大性阐明
措施1 3 – 5的巨大性是O ( n2 )，任何最短路径算法必需至少对每条边查抄一次，因为任何一条边都有大概在最短路径中。因此这种算法的最小大概时间为O ( e )。由于利用淹灭连接矩阵来描写图，仅抉择哪条边在有向图中就需O ( n2 )的时间。因此，回收这种描写要领的算法需耗费O ( n2 )的时间。不外措施1 3 – 5作了优化（常数因子级）。纵然改变连接表，也只会使最后一个f o r轮回的总时间降为O ( e )（因为只有与i 连接的极点的d 值改变）。从L中选择及删除最小间隔的极点所需总时间仍然是O( n2 )。
