一、本文的由来
数据结构老师布置了一个题目,要求我们写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];
}
}
}
}
五、视频链接