Floyd算法是一个经典的动态规划算法，它又被称为插点法。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。Floyd算法是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法,算法目标是寻找从点i到点j的最短路径。

从任意节点i到任意节点j的最短路径不外乎2种可能，1是直接从i到j，2是从i经过若干个节点k到j。所以，算法假设Dis(i,j)为节点u到节点v的最短路径的距离，对于每一个节点k，算法检查Dis(i,k) + Dis(k,j) < Dis(i,j)是否成立，如果成立，证明从i到k再到j的路径比i直接到j的路径短，便设置Dis(i,j) = Dis(i,k) + Dis(k,j)，这样一来，当遍历完所有节点k，Dis(i,j)中记录的便是i到j的最短路径的距离。

以下纯手工操作~

上面最后有个问题，更正一下，应该是

eg：d13 = 45，R13 = 5，R15 = 5（或者）R51 = 1，也就是13之间经过5，然后再看15之间有没有经过其他点，如果经过了继续查表，由于通过R15或R51可以看出，他们之间没有经过其他点，所以最短路径为1-》5-》3，最短距离为45.

编程求解几座城市之间的最短距离，以及最短距离所经过的城市。

floyd.c：