Floyed求多源最短路径
4970+
作者:crxis 发布:2017-07-27 分类:最短路径
题目大意:用邻接矩阵给出图中各点的直接距离,计算各个点之间的最短路程,并把这条路输出来。
输入测试
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判断是否连通。