基于C++实现的每对结点之间的最短路径(Floyd-Warshall算法)

Pubertyly

发布日期: 2019-03-13 18:15:19 浏览量: 445
评分:
star star star star star star star star star_border star_border
*转载请注明来自write-bug.com

1、实验题

每对结点之间的最短路径问题(Floyd-Warshall算法):

G = ( V, E)是一个有n 个结点的有向图。补充ALL-PATHS算法,增加前驱矩阵,使得在求出结点间的最短路径长度矩阵A后,能够推导出每对结点间的最短路径。

2、设计思路

这里要求的是有向图中每一对节点之间的最短路径,用Floyd_WallShall算法解决此问题。

从节点v到节点u的最短路径有2种可能:直接从v到u,或者从v出发,经过一条包含若干个节点的路径,到达u。

设D(i,j)是当前已求得的从节点u到节点v的最短路径长度,其中i、j分别为两个节点的序号。现在需要继续计算以更新最短路径。对于图中的每个点w,判断d(i,k)+d(k,j)与d(i,j)的大小关系,若前者小于后者,说明找到了一条新路径,将该值替换原来的最短路径长度。如此往复,遍历所有的节点,最终将得到一条最短的路径。

3、运行演示

运行程序,输出每对节点间的路径和路径长度。

上传的附件 cloud_download 基于C++实现的每对结点之间的最短路径(Floyd-Warshall算法).7z ( 44.56kb, 1次下载 )
error_outline 下载需要5点积分

发送私信

走在一起是缘分,一起在走是幸福

18
文章数
20
评论数
最近文章
eject