图论------弗洛伊德(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行，理解不了直接背下来也是很容易的，可以在往后的实践中逐渐搞明白。