弗洛伊德算法求路径

弗洛伊德算法的核心目标是计算图中任意两点之间的最短路径。以学校为例，若从一教前往四教，直接行走的距离为10公里，但若选择经过风雨操场，则总距离可能缩短至8公里。进一步而言，若再经过数图这一节点，总距离甚至可能仅需6公里。这表明，在路径规划过程中引入中间节点往往能够有效减少整体行程。

以图中给出的例子来看，假设当前需要从点1到达点3，若直接连接则需6步。然而通过引入中间节点2，即采用1→2→3的路径方式，则只需5步即可完成。那么如何实现这种优化呢？此时只需要对当前路径与经由节点2后的路径进行比较，并取其中较小值即可实现，具体公式为：min(e[i][j], e[i][2] + e[2][j])。

其中，“i→j”表示从点i到点j的直接连接关系。

进一步地，我们可将这一思路推广至整个图中。即对于每一对点i和j，在考虑是否经过节点2后，判断其路径长度是否会进一步缩短。

    //经过2号顶点
    for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
        if (e[i][j] > e[i][2]+e[2][j])