导航:首页 > 源码编译 > 图论顶点间路径长度算法

图论顶点间路径长度算法

发布时间:2024-11-07 23:58:52

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

在交通网络中,常常会提出许多这样的问题:两地之间是否有路相通?在有多条通路的情况下,哪一条最近?哪一条花费最少等。交通网络可以用带权图表示,图中顶点表示域镇,边表示两城之间的道路,边上权值可表示两城镇间的距离,交通费用或途中所需的时间等。
以上提出的问题就是带权图中求最短路径的问题,即求两个顶点间长度最短的路径。
最短路径问题的提法很多。在这里仅讨论单源最短路径问题:即已知有向图(带权),我们希望找出从某个源点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] 表示有向边<i,j>的权。若不存在有向边<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之间的最短路径的前驱顶点。

阅读全文

与图论顶点间路径长度算法相关的资料

热点内容
鄞州繁裕三村附近启蒙编程学校 浏览:555
单片机里code什么意思 浏览:182
linux修改umask 浏览:536
编程锁的发展 浏览:346
唯词app怎么改密码 浏览:72
魔兽世界表情命令 浏览:985
智能还款信用卡源码 浏览:554
zoo文件夹 浏览:762
安卓2k21如何下载 浏览:648
某年某月的天数python 浏览:912
广度优先算法的复杂度 浏览:399
系统重装网站源码 浏览:152
相册加密相片 浏览:297
美国正常化行政命令 浏览:277
中级审计师教材pdf 浏览:696
wps中pdf旋转 浏览:600
getex命令 浏览:190
云闪付和农行卡app怎么授权 浏览:123
羁绊命令 浏览:51
解压视频怪兽大全 浏览:964