《贪婪算法---单源最短路径》由会员分享，可在线阅读，更多相关《贪婪算法---单源最短路径（6页珍藏版）》请在金锄头文库上搜索。
1、贪婪算法贪婪算法-单源最短路径单源最短路径单源最短路径在这个问题中，给出有向图 G，它的每条边都有一个非负的长度（耗费） a i j ，路径的长度即为此路径所经过的边的长度之和。对于给定的源顶点 s，需找出从它到图中其他任意顶点（称为目的）的最短路径。图 13-10a 给出了一个具有五个顶点的有向图，各边上的数即为长度。假设源顶点 s 为 1，从顶点 1 出发的最短路径按路径长度顺序列在图 13-10b 中，每条路径前面的数字为路径的长度。利用 E. Dijkstra 发明的贪婪算法可以解决最短路径问题，它通过分步方法求出最短路径。每一步产生一个到达新的目的顶点的最短路径。下一步所能达到的目的
2、顶点通过如下贪婪准则选取：在还未产生最短路径的顶点中，选择路径长度最短的目的顶点。也就是说，D i j k s t r a 的方法按路径长度顺序产生最短路径。首先最初产生从 s 到它自身的路径，这条路径没有边，其长度为0。在贪婪算法的每一步中，产生下一个最短路径。一种方法是在目前已产生的最短路径中加入一条可行的最短的边，结果产生的新路径是原先产生的最短路径加上一条边。这种策略并不总是起作用。另一种方法是在目前产生的每一条最短路径中，考虑加入一条最短的边，再从所有这些边中先选择最短的，这种策略即是 D i j k s t r a 算法。可以验证按长度顺序产生最短路径时，下一条最短路径总是由一条已
3、产生的最短路径加上一条边形成。实际上，下一条最短路径总是由已产生的最短路径再扩充一条最短的边得到的，且这条路径所到达的顶点其最短路径还未产生。例如在图 1 3 - 1 0 中，b 中第二条路径是第一条路径扩充一条边形成的；第三条路径则是第二条路径扩充一条边；第四条路径是第一条路径扩充一条边；第五条路径是第三条路径扩充一条边。通过上述观察可用一种简便的方法来存储最短路径。可以利用数组p，p i 给出从 s 到达 i 的路径中顶点 i 前面的那个顶点。在本例中 p 1 : 5 = 0 , 1 , 1 , 3 , 4 。从 s 到顶点 i 的路径可反向创建。从 i 出发按 pi,ppi,pppi,
4、.的顺序，直到到达顶点 s 或 0。在本例中，如果从 i = 5 开始，则顶点序列为 pi=4, p4=3, p3=1=s，因此路径为 1 , 3 , 4 , 5。为能方便地按长度递增的顺序产生最短路径，定义 d i 为在已产生的最短路径中加入一条最短边的长度，从而使得扩充的路径到达顶点 i。最初，仅有从 s 到 s 的一条长度为 0 的路径，这时对于每个顶点 i，d i 等于 a s i （a 是有向图的长度邻接矩阵） 。为产生下一条路径，需要选择还未产生最短路径的下一个节点，在这些节点中 d 值最小的即为下一条路径的终点。当获得一条新的最短路径后，由于新的最短路径可能会产生更小的 d 值，
5、因此有些顶点的 d 值可能会发生变化。综上所述，可以得到图 1 3 - 11 所示的伪代码， 1) 将与 s 邻接的所有顶点的 p 初始化为 s，这个初始化用于记录当前可用的最好信息。也就是说，从 s 到 i 的最短路径，即是由 s 到它自身那条路径再扩充一条边得到。当找到更短的路径时， p i 值将被更新。若产生了下一条最短路径，需要根据路径的扩充边来更新 d 的值。1) 初始化 di =as i （1in） ，对于邻接于 s 的所有顶点 i，置 pi =s, 对于其余的顶点置 pi = 0；对于 pi0 的所有顶点建立 L 表。2) 若 L 为空，终止，否则转至 3 )。3) 从 L 中删
6、除 d 值最小的顶点。4) 对于与 i 邻接的所有还未到达的顶点 j，更新 d j 值为 m i nd j , di +ai j ；若 d j 发生了变化且 j 还未在 L 中，则置 p j = 1，并将 j 加入 L，转至 2。图 1 - 11 最短路径算法的描述1. 数据结构的选择我们需要为未到达的顶点列表 L 选择一个数据结构。从 L 中可以选出 d 值最小的顶点。如果 L 用最小堆（见 9 . 3 节）来维护，则这种选取可在对数时间内完成。由于 3) 的执行次数为 O ( n )，所以所需时间为 O ( n l o g n )。由于扩充一条边产生新的最短路径时，可能使未到达的顶点产生更
7、小的 d 值，所以在 4) 中可能需要改变一些 d 值。虽然算法中的减操作并不是标准的最小堆操作，但它能在对数时间内完成。由于执行减操作的总次数为： O(有向图中的边数)= O ( n2 )，因此执行减操作的总时间为 O ( n2 l o g n )。若 L 用无序的链表来维护，则 3) 与 4) 花费的时间为 O ( n2 )，3) 的每次执行需 O(|L | ) =O( n )的时间，每次减操作需( 1 )的时间（需要减去 dj 的值，但链表不用改变） 。利用无序链表将图 1 - 11 的伪代码细化为程序 1 3 - 5，其中使用了 C h a i n (见程序 3 - 8 )和 C h
8、a i n I t e r a t o r 类（见程序 3 - 1 8） 。程序 13-5 最短路径程序templatevoid AdjacencyWDigraph:ShortestPaths(int s, T d, int p)/ 寻找从顶点 s 出发的最短路径, 在 d 中返回最短距离/ 在 p 中返回前继顶点if (s n) throw OutOfBounds();Chain L; / 路径可到达顶点的列表ChainIterator I;/ 初始化 d, p, Lfor (int i = 1; i di + aij) / 减小 d j dj = di + aij;/ 将 j 加入 Lif
9、 (!pj) L.Insert(0,j);pj = i;若 N o E d g e 足够大，使得没有最短路径的长度大于或等于 N o E d g e，则最后一个 for 循环的 i f 条件可简化为：if (dj di + aij) NoEdge 的值应在能使 dj+aij 不会产生溢出的范围内。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 )。
