首页 » 算法技术手册 » 算法技术手册全文在线阅读

《算法技术手册》变种

关灯直达底部

如果最短的航线有许多,那么你可能解决了错误的问题。例如,如果我们希望减少油料消耗,那么自然而然我们会选择最短路径。但是在着陆和起飞时油料消耗也是必须考虑的因素。你必须考虑到起飞和降落时额外的油料消耗,并且把这个额外的消耗加入到distance(say,D)中。然后再寻找最短路径。

在这个问题上,我们能够找到最短路径。在其他的应用中,我们可以用时间(例如在网络中尽可能快速地投递网络包)或者开销(例如商务旅行中寻找最便宜的从S t.Johnsbury去Waco的交通工具)代替距离。这些问题同样也可以抽象成最短路径。

如果我们需要在网络的两点之间传递数据包,在我们已经知道正确传递数据包的概率,那么寻找到最可靠的路径很有必要。路径正确传递数据包的概率是每条边的概率之积。我们创建一个新图,每条边的概率将原图中的概率取负对数。这样,在这个新图中,最短路径就是原图中的最可靠路径。

Dijkstra算法不能够应用于有负权边的图。但是,Bellman-Ford(如图6-16和例6-6所示)可以在不存在负值环的情况下使用。也就是说,不存在一个环,其边权值总和为负数。在这样的环存在的情况下,“最短路径”的概念是没有意义的。虽然图6-13包含一个环{1,3,2},但是边权值为正,所以Bellman-Ford和Dijkstra算法都能够适用。

图 6-16 Bellman-Ford详解

例6-6:使用Bellman-Ford解单源最短路径

Bellman-Ford算法很直观地在图中推进n次,寻找是否存在一条边(u,v),能够在给定dist[u]和边(u,v)的权值下,更新dist[v]。我们需要至少n-1次推进,例如,在极端情况下,从源点s到某个顶点v的最短路径需要通过图中所有的顶点。另外,因为边可以以任意顺序访问,使用n-1次推进就能够确保所有的缩减路能够被发现。事实上,以不同的顺序访问边将会导致一个不同的计算dist值过程。图6-17所示的是在两个不同的图上执行Bellman-Ford算法,这两个图的区别在于标记为v4和v1的顶点。但是如果你考虑重标记的话,两个执行过程都能够得到同样的结果。

图 6-17 不同的Bellman-Ford执行过程,能够得到同样的结果

如果存在负环,Bellman-Ford是不能正常工作的。为了检测负环,我们执行一个循环n次(不止一次),如果有调整dist的值,那么就存在负环。从嵌入的循环中可以很明显地看出来,Bellman-Ford的性能是O(V*E)。