Floyd算法--多源最短路径

首先我们知道，要求一个图中两个顶点中的最短路径，除了计算出这两个顶点的直接路径，还可以借助其他的顶点作为“跳板”，
来看看能不能使得这两点的路径变短，来看一个例子：

假设这是一个给定的无向图图，图中共有4个顶点（A、B、C、D），
图中的边共有：A-->B(10)、A-->C(2)、C-->B(6)、C-->D(1)、D-->B(2)五条边（严格来说有10条边，因为是无向图），
顶点C和顶点B相连：A-->C-->B的距离一共是8，明显比顶点A直接到顶点B更短。
再观察一下，我们还可以发现顶点C和顶点D直接相连，D顶点和顶点B直接相连：A-->C-->D-->B的距离一共是5，又是一条更短的路径！
之后我们找不到顶点A到顶点B还有比距离5更短的路径了，那么，在这个图中顶点A到顶点B的最短路径就是5

for(int i = 1; i <= n; i++)
{
    if(e[1][2] > e[1][i] + e[i][2])
    {
        /* 这段代码的意思是：循环遍历图中的所有顶点
        * 如果利用图中的其它顶点可以使得顶点A到顶点B的路径变短，
        * 那么更新顶点A到顶点B的最短路径
        */
        e[1][2] = e[1][i] + e[i][2]; 
    }
}

for(int i = 1; i <= n; i++)
{
    for(int j = 1; j <= n; j++)
    {
        for(int k = 1; k <= n; k++)
        {
            if(e[j][k] > e[j][i] + e[i][k])
            {
                e[j][k] = e[j][i] + e[i][k];
            }
        }
    }
}

#include <iostream>
using namespace std;
const int inf = 999999999;  // 模拟无穷大（表示图的两个顶点没有直接相连）
const int N = 1000; // 图的顶点个数最多为1000个

int e[N][N];    // 图的邻接矩阵

int main()
{
    int n, m;  // 图的顶点个数和边的条数(其实叫度的数目会更好)
    cin >> n >> m;
    for(int i = 1; i <= n; i++) // 初始化图
    {
        for(int j = 1; j <= n; j++)
        {
            if(i == j)
            {
                e[i][j] = 0;
            }
            else
            {
                e[i][j] = inf;
            }
        }
    }
    int x, y, w;    // 记录图的每一条边的信息
    for(int i = 1; i <= m; i++)
    {
        cin >> x >> y >> w;
        e[x][y] = e[y][x] = w;
    }

    for(int i = 1; i <= n; i++) // Floyd算法核心代码
    {
        for(int j = 1; j <= n; j++)
        {
            for(int k = 1; k <= n; k++)
            {
                if(e[j][k] > e[j][i] + e[i][k])
                {
                    e[j][k] = e[j][i] + e[i][k];
                }
            }
        }
    }

    for(int i = 1; i <= n; i++) // 输出算法结束后的图的邻接矩阵信息
    {
        for(int j = 1; j <= n; j++)
        {
            cout.width(4);
            cout << e[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}