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

图论顶点间路径长度算法

发布时间: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之间的最短路径的前驱顶点。

阅读全文

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

热点内容
如何改服务器子网掩码 浏览:560
python写满磁盘 浏览:608
外省违章怎么交罚款app 浏览:771
如何提取wml源码 浏览:677
程序员陆漓出国了吗 浏览:991
python爬二级链接 浏览:627
程序员被老总骂 浏览:582
如何在win7下连接网络连接到服务器 浏览:129
服务器如何进入光盘启动不了 浏览:754
什么学生云服务器最便宜 浏览:341
苹果手机怎么设置app消息提示音 浏览:525
把四个文件夹释放到安装目录 浏览:217
一女程序员喜欢男程序员 浏览:867
压缩加密怎么做 浏览:743
苹果换手机app怎么转到新手机 浏览:28
企业在线直播源码 浏览:256
怎么给信号加密 浏览:801
直播系统源码图片 浏览:76
ge天然气压缩机 浏览:980
新建文件夹内容在哪里找 浏览:571