floyed_strongxu的专栏

你是否正在寻找关于floyed的内容？让我把最俱价值的东西奉献给你：

其实这个算法很简单啦，记不住各种算法的名字

从这个链接拷过来的

从有向图的带权的邻接矩阵cost出发，对有向图的n个顶点加以编号，若从i到j有弧（i=1，2，...，n，j=1，2，...，n），则从i到j存在一条长度为cost(i，j)的路线。但该路径不一定是最短路径，尚需修改，修改的方法是进行n次试探。首先考虑路径（i，1，j）（即在i，j中插进点1），看〈i，1〉，〈1，j〉是否存在，若存在，再比较（i，j）与（i，1，j）这两条路径，长度较短者为当前求得的最短路径。于是这条求得的最短路径的中间点序号不大于1。然后再在各对点i，j中插进一个点2，看〈i，...，2〉，〈2，...，j〉是否存在，若不存在，那么当前的最短路径仍是上次求得的中间点序号不大于1的最短路径；若存在，则将（i，...，2，j）的路径与前次求出的中间点序号不大于1的最短路径进行比较，取长度较短者为当前的最短路径。这样，这次求得的最短路径的中间点序号不大于2。......，依次类推，直至求得从i到j的最短路径。

floyed的主程序段很精简，就是3重循环，。

for (k = 0; k < n; k )

for (i = 0; i < n; i )

if (i != k) for (j = 0; j < n; j )

if ((j != i && j != k) && (map[i][k] map[k][j] < map[i][j]))

map[i][j] = map[i][k] map[k][j];

北大ACM题库里的2263题，实现这个算法就OK了

以上就是关于floyed的全部内容，相信你一定会非常满意。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/shenmilingyu/article-350-1.html