在这个问题中给出有向图G它的每条边都有一个非负的长度(耗费) a [i ][ j ]路径的长度即为此路径所经过的边的长度之和对于给定的源顶点s需找出从它到图中其他任意顶点(称为目的)的最短路径图a 给出了一个具有五个顶点的有向图各边上的数即为长度假设源顶点s 为从顶点出发的最短路径按路径长度顺序列在图b 中每条路径前面的数字为路径的长度
利用E Dijkstra发明的贪婪算法可以解决最短路径问题它通过分步方法求出最短路径每一步产生一个到达新的目的顶点的最短路径下一步所能达到的目的顶点通过如下贪婪准则选取在还未产生最短路径的顶点中选择路径长度最短的目的顶点也就是说 D i j k s t r a的方法按路径长度顺序产生最短路径
首先最初产生从s 到它自身的路径这条路径没有边其长度为在贪婪算法的每一步中产生下一个最短路径一种方法是在目前已产生的最短路径中加入一条可行的最短的边结果产生的新路径是原先产生的最短路径加上一条边这种策略并不总是起作用另一种方法是在目前产生的每一条最短路径中考虑加入一条最短的边再从所有这些边中先选择最短的这种策略即是D i j k s t r a算法
可以验证按长度顺序产生最短路径时下一条最短路径总是由一条已产生的最短路径加上一条边形成实际上下一条最短路径总是由已产生的最短路径再扩充一条最短的边得到的且这条路径所到达的顶点其最短路径还未产生例如在图 中b 中第二条路径是第一条路径扩充一条边形成的;第三条路径则是第二条路径扩充一条边;第四条路径是第一条路径扩充一条边;第五条路径是第三条路径扩充一条边
通过上述观察可用一种简便的方法来存储最短路径可以利用数组pp [ i ]给出从s 到达i的路径中顶点i 前面的那个顶点在本例中p [ : ] = [ ]从s 到顶点i 的路径可反向创建从i 出发按p[i]p[p[i]]p[p[p[i]]] 的顺序直到到达顶点s 或在本例中如果从i = 开始则顶点序列为p[i]= p[]= p[]==s因此路径为
为能方便地按长度递增的顺序产生最短路径定义d [ i ]为在已产生的最短路径中加入一条最短边的长度从而使得扩充的路径到达顶点i最初仅有从s 到s 的一条长度为的路径这时对于每个顶点id [ i ]等于a [ s ] [ i ](a 是有向图的长度邻接矩阵)为产生下一条路径需要选择还未产生最短路径的下一个节点在这些节点中d值最小的即为下一条路径的终点当获得一条新的最短路径后由于新的最短路径可能会产生更小的d值因此有些顶点的d值可能会发生变化
综上所述可以得到图 所示的伪代码 ) 将与s 邻接的所有顶点的p 初始化为s这个初始化用于记录当前可用的最好信息也就是说从s 到i 的最短路径即是由s到它自身那条路径再扩充一条边得到当找到更短的路径时 p [ i ]值将被更新若产生了下一条最短路径需要根据路径的扩充边来更新d 的值
) 初始化d[i ] =a[s] [i ](≤i≤n)
对于邻接于s的所有顶点i置p[i ] =s 对于其余的顶点置p[i ] = ;
对于p[i]≠的所有顶点建立L表
) 若L为空终止否则转至 )
) 从L中删除d值最小的顶点
) 对于与i 邻接的所有还未到达的顶点j更新d[ j ]值为m i n{d[ j ] d[i ] +a[i ][ j ] };若d[ j ]发生了变化且j 还未
在L中则置p[ j ] = 并将j 加入L转至
图 最短路径算法的描述
数据结构的选择
我们需要为未到达的顶点列表L选择一个数据结构从L中可以选出d 值最小的顶点如果L用最小堆(见 节)来维护则这种选取可在对数时间内完成由于) 的执行次数为O ( n )所以所需时间为O ( n l o g n )由于扩充一条边产生新的最短路径时可能使未到达的顶点产生更小的d 值所以在) 中可能需要改变一些d 值虽然算法中的减操作并不是标准的最小堆操作但它能在对数时间内完成由于执行减操作的总次数为 O(有向图中的边数)= O ( n )因此执行减操作的总时间为O ( n l o g n )
若L用无序的链表来维护则) 与) 花费的时间为O ( n )) 的每次执行需O(|L | ) =O( n )的时间每次减操作需( )的时间(需要减去d[j] 的值但链表不用改变)利用无序链表将图 的伪代码细化为程序 其中使用了C h a i n (见程序 )和C h a i n I t e r a t o r类(见程序 )
程序 最短路径程序
template
void AdjacencyWDigraph ::ShortestPaths(int s T d[] int p[])
{// 寻找从顶点s出发的最短路径 在d中返回最短距离
// 在p中返回前继顶点
if (s < || s > n) throw OutOfBounds();
Chain L; // 路径可到达顶点的列表
ChainIterator I;
// 初始化d p L
for (int i = ; i <= n; i++){
d[i] = a[s][i];
if (d[i] == NoEdge) p[i] = ;
else {p[i] = s;
L I n s e r t ( i ) ; }
}
// 更新d p
while (!LIsEmpty()) {// 寻找具有最小d的顶点v
int *v = IInitialize(L);
int *w = INext();
while (w) {
if (d[*w] < d[*v]) v = w;
w = INext();}
// 从L中删除通向顶点v的下一最短路径并更新d
int i = *v;
L D e l e t e ( * v ) ;
for (int j = ; 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]) LInsert(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] 不会产生溢出的范围内
复杂性分析
程序 的复杂性是O ( n )任何最短路径算法必须至少对每条边检查一次因为任何一条边都有可能在最短路径中因此这种算法的最小可能时间为O ( e )由于使用耗费邻接矩阵来描述图仅决定哪条边在有向图中就需O ( n )的时间因此采用这种描述方法的算法需花费O ( n )的时间不过程序 作了优化(常数因子级)即使改变邻接表也只会使最后一个f o r循环的总时间降为O ( e )(因为只有与i 邻接的顶点的d 值改变)从L中选择及删除最小距离的顶点所需总时间仍然是O( n )
