题目大意:用邻接矩阵给出图中各点的直接距离,计算各个点之间的最短路程,并把这条路输出来.
n个点,可以用n次迪杰斯特拉,但不如弗洛伊德算法方便.
如果用弗洛伊德算法求多源最短路径?在最外层枚举路径中间编号最大的点k,接着里面嵌套循环枚举图上两两互不相同的点i和j,如果i->k加上k->j比i->j更短,那么更新i->j的距离,此时,i->k和k->i的距离是已知的,因为i->k和k->j中间的所有点,都不比k大,任意两点路径上的点都比k小的最短路已经上之前算出来了.
不管是无向图,还是有向图,都适用,即使你要判断两点的连通性,也是可以的,如把mp数组改成布尔型,用位运算更新连通性,或者根据距离是否inf判断是否连通.
Floyed求多源最短路径:等您坐沙发呢!