求有向图两个顶点间的最短路径的方法,用简单语言或举例描述.

Question

求有向图两个顶点间的最短路径的方法,用简单语言或举例描述.

Answer 1

在交通网络中,常常会提出许多这样的问题：两地之间是否有路相通?在有多条通路的情况下,哪一条最近?哪一条花费最少等.交通网络可以用带权图表示,图中顶点表示域镇,边表示两城之间的道路,边上权值可表示两城镇间的距离,交通费用或途中所需的时间等.
　　以上提出的问题就是带权图中求最短路径的问题,即求两个顶点间长度最短的路径.
　　最短路径问题的提法很多.在这里仅讨论单源最短路径问题：即已知有向图(带权),我们希望找出从某个源点S∈V到G中其余各顶点的最短路径.
　　例如：下图(有向图G14),假定以v1为源点,则其它各顶点的最短路径如下表所示：
　　
　　　　　　　　　　　　　　　　　　　　图 G14
　　从有向图可看出,顶点v1到v4的路径有3条：(v1,v2,v4),(v1,v4),(v1,v3,v2,v4 ),其路径长度分别为：15,20和10.因此v1到v4的最短路径为(v1,v3,v2,v4 ).
　　为了叙述方便,我们把路径上的开始点称为源点,路径的最后一个顶点为终点.
　　那么,如何求得给定有向图的单源最短路径呢?迪杰斯特拉(Dijkstra)提出按路径长度递增产生诸顶点的最短路径算法,称之为迪杰斯特拉算法.
　　迪杰斯特拉算法求最短路径的实现思想是：设有向图G=(V,E),其中,V={1,2,…,n},cost是表示G的邻接矩阵,cost[i][j] 表示有向边的权.若不存在有向边,则cost[i][j]的权为无穷大(这里取值为32767).设S是一个集合,其中的每个元素表示一个顶点,从源点到这些顶点的最短距离已经求出.设顶点v1为源点,集合S的初态只包含顶点v1.数组dist记录从源点到其他各顶点当前的最短距离,其初值为dist[i]=cost[v1][i],i=2,…,n.从S之外的顶点集合V-S 中选出一个顶点w,使dist[w]的值最小.于是从源点到达w只通过S 中的顶点,把w加入集合S中调整dist中记录的从源点到V-S中每个顶点v的距离：从原来的dist[v] 和dist[w]+cost[w][v]中选择较小的值作为新的dist[v].重复上述过程,直到S中包含V中其余顶点的最短路径.
　　最终结果是：S记录了从源点到该顶点存在最短路径的顶点集合,数组dist记录了从源点到 V中其余各顶点之间的最短路径,path是最短路径的路径数组,其中path[i] 表示从源点到顶点i之间的最短路径的前驱顶点.