图论------弗洛伊德(Floyd-Warshall)算法

题目描述：

在每年的校赛里，所有进入决赛的同学都会获得一件很漂亮的  T-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候，却是非常累的！所以现在他们想要寻找最短的从商店到赛场的路线，你可以帮助他们吗？

输入输出格式
输入格式
第一行是两个整数 N,M，N 表示成都的大街上有几个路口，标号为 1 的路口是商店所在地，标号为 N 的路口是赛场所在地，M 则表示在成都有几条路。
接下来 M 行，每行包括三个整数 A，B，C，表示在路口 A 与路口 B 之间有一条路，我们的工作人员需要 C 分钟的时间走过这条路。
输入保证至少存在 1 条商店到赛场的路线。
输出格式
输出一行，表示工作人员从商店走到赛场的最短时间。

输入输出样例1
输入
3 3
1 2 5
2 3 5
3 1 2
输出
2

输入输出样例2
输入
2 1
1 2 3
输出
3

具体代码：

        

#include<stdio.h>

int main(void)

{

    int arr[100][100] = { 0 };//构建图

    int n, m;

    scanf("%d%d", &n, &m);

    int a, b,c;

    for (int i = 1; i <= n; i++)

        for (int j = 1; j <= n; j++)

            if (i == j)

                arr[i][j] = 0;

            else

                arr[i][j] = 99999999;//初始化图。

    for (int i = 0; i < m; i++)

    {

        scanf("%d%d%d", &a, &b, &c);

        arr[a][b] = c;

        arr[b][a] = c;

    }//根据输入为图赋值。

    for (int k = 1; k <= n; k++)

        for (int i = 1; i <= n; i++)

            for (int j = 1; j <= n; j++)

                if (arr[i][j] > arr[i][k] + arr[k][j]&&arr[i][k]<99999999&&arr[k][j]<99999999)

                    arr[i][j] = arr[i][k] + arr[k][j];//Floyd—warshall核心代码。

                  

    printf("%d", arr[1][n]);//打印结果

}

代码解析：

        关于构件图和为图初始化赋值是上节课的答案，在此我们就不进行讲述。

        实际上Floyd-Warshall算法是较为容易理解的算法，因其核心代码只有5行。

        

for (int k = 1; k <= n; k++)

        for (int i = 1; i <= n; i++)

            for (int j = 1; j <= n; j++)

                if (arr[i][j] > arr[i][k] + arr[k][j]&&arr[i][k]<99999999&&arr[k][j]<99999999)

                    arr[i][j] = arr[i][k] + arr[k][j];

        讲述起来很简单，我们先看后四行代码，假设k = 1.

        

for (int i = 1; i <= n; i++)

            for (int j = 1; j <= n; j++)

                if (arr[i][j] > arr[i][1] + arr[1][j]&&arr[i][1]<99999999&&arr[1][j]<99999999)

                    arr[i][j] = arr[i][k] + arr[k][j];

        arr[i][1]+arr[1][j]表示i通过1到j的路程。

        如果从i直接到j的路程比通过1的路程要长的化，更新arr[i][j]的值变短。如果再来一次这段代码，这次k值为2，表示让arr[i][j]与让i通过1，2到j的值进行比较更新arr[i][j],然后继续让k等于3，4，5，，，，，n，这样就能更新全图，可以得到任意两点的最短路径。

        arr[i][1]<99999999&&arr[1][j]<99999999而这也是个判断条件，如果这两点有任意一个路不通，就不执行最后一条语句，这也很容易理解，如果路不通也就不能走了。

温馨提示：

        这段代码并不是专门求单源最短路径，而是可以得出任意两点的最短路径。

        这段代码核心只有5行，理解不了直接背下来也是很容易的，可以在往后的实践中逐渐搞明白。