[分享]单源最短路径

frogfish

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

readj

好

christy

谢谢