当前位置:首页 > 图论 > 最短路径 > 正文
Floyed求多源最短路径
4970+

题目大意:用邻接矩阵给出图中各点的直接距离,计算各个点之间的最短路程,并把这条路输出来。

输入测试

4
1000 5 1000 1000
50 1000 15 5
30 1000 1000 15
15 1000 5 1000

输出结果

i -> j	Dis	Path
1 -> 2	5	1 -> 2
1 -> 3	15	1 -> 2 -> 4 -> 3
1 -> 4	10	1 -> 2 -> 4
2 -> 1	20	2 -> 4 -> 1
2 -> 3	10	2 -> 4 -> 3
2 -> 4	5	2 -> 4
3 -> 1	30	3 -> 1
3 -> 2	35	3 -> 1 -> 2
3 -> 4	15	3 -> 4
4 -> 1	15	4 -> 1
4 -> 2	20	4 -> 1 -> 2
4 -> 3	5	4 -> 3

解题思路

n个点,可以用n次迪杰斯特拉,但不如弗洛伊德算法方便。

如果用弗洛伊德算法求多源最短路径?在最外层枚举路径中间编号最大的点k,接着里面嵌套循环枚举图上两两互不相同的点i和j,如果i->k加上k->j比i->j更短,那么更新i->j的距离,此时,i->k和k->i的距离是已知的,因为i->k和k->j中间的所有点,都不比k大,任意两点路径上的点都比k小的最短路已经上之前算出来了。

如何记录路径?用一个二维数组mp[i][j]记录i到j的路径上前一个点是谁,如果这个点是x,那么接下来求的上一个点就是mp[i][x]。如果更新?如果找到更短路,中间点是k,即i->k->j,那么i->j路上j的前驱就是k->j路上的j的前驱。

不管是无向图,还是有向图,都适用,即使你要判断两点的连通性,也是可以的,如把mp数组改成布尔型,用位运算更新连通性,或者根据距离是否inf判断是否连通。

程序实现

About

坚决不Copy代码!

本文标签:,,,,,,

Floyed求多源最短路径:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!