一、本文的由来
数据结构老师布置了一个题目，要求我们写Floyd算法的实现过程的PPT（我不理解，孩子又不是教技的娃娃，为啥还要讲课做PPT嘞）
好吧~为了上课cue到我的时候，不会被发现我在摸鱼，我还是康了康视频，后面会把视频链接附在最后，有兴趣的同学可以康康
二、简单介绍弗洛伊德和迪杰斯特拉的渊源
-
Floyd的算法由来，应该是在
迪杰斯特拉算法的基础
之上，对图的最短路径的一个更深的理解。 -
迪杰斯特拉算法主要是对于俩点之间的距离，比如
图1
中的0到1，0到2，0到3，但是它不涉及任意俩点之间的一个距离问题 -
这样就导致我们又研究出一种适合于
任意俩点之间距离
的一个算法，被我们称为
Floyd算法
，顾名思义，肯定是弗洛伊德研究出来的嚯嚯嚯
图1
三、算法思想
1、文字解释
弗洛伊德算法首先是
构建俩个数组
-
Av
A_v
A
v
：初始值为图的邻接矩阵 -
Pa
t
h
v
Path_v
P
a
t
h
v
：记录俩点之间的最短路径上的中间点（初始值都为-1） - 下标v：顶点v
具体的实现手段
（算法思想）
1、每一个顶点v，与任意一个顶点队（i，j），
其中
i≠j，v≠i，v≠j
如果存在
A[i][j] > A[v][j] + A[i][v]
则将
A[i][j]
的值换为：
A[v][j] + A[i][v]
，同时
path[i][j]
的值也换为
v
2、然后依此对每一个顶点进行上述操作
3、最后得到
path数组的值
，就是咱们需要的
最短路径的顶点坐标
，再根据
顶点，查找对应的A数组的值
（权值），就能得到所谓的
最短路径
4、最终俩个数组的意义
-
二维数组A：对应的是更新过后的俩点之间
最短路径的一个
权值
-
二维数组Path：对应的是更新过后俩点之间的
最短路径所经历的
点坐标
【式子的意义】
A[i][j] > A[v][j] + A[i][v]
这个公式的目的就是求出最短的那个路径，比如在
i=1，j=2，v=3的时候，只要上述的比较公式成立，就证明了目前1到2的最短路径为1->3->2，而不是直接的1->2
2、图示解释
用一个略微简单的例子（4个顶点）
最开始的数组
当顶点为1的时候，遍历的次序
当顶点为2的时候，遍历的次序
当顶点为3的时候，遍历的次序
当顶点为4的时候，遍历的次序
最终的A和Path图像 +例子
四、算法代码
for (k = 0; k < G.vexnum; k++)
{
for (i = 0; i < G.vexnum; i++)
{
for (j = 0; j < G.vexnum; j++)
{
// 如果经过下标为k顶点路径比原两点间路径更短，则更新dist[i][j]和path[i][j]
tmp = (dist[i][k]==INF || dist[k][j]==INF) ? INF : (dist[i][k] + dist[k][j]);
if (dist[i][j] > tmp)
{
// "i到j最短路径"对应的值设，为更小的一个(即经过k)
dist[i][j] = tmp;
// "i到j最短路径"对应的路径，经过k
path[i][j] = path[i][k];
}
}
}
}
五、视频链接