Floyd算法（弗洛伊德）基本实现以及代码

一、本文的由来

数据结构老师布置了一个题目，要求我们写Floyd算法的实现过程的PPT（我不理解，孩子又不是教技的娃娃，为啥还要讲课做PPT嘞）
好吧~为了上课cue到我的时候，不会被发现我在摸鱼，我还是康了康视频，后面会把视频链接附在最后，有兴趣的同学可以康康

二、简单介绍弗洛伊德和迪杰斯特拉的渊源

• Floyd的算法由来，应该是在迪杰斯特拉算法的基础之上，对图的最短路径的一个更深的理解。

• 迪杰斯特拉算法主要是对于俩点之间的距离，比如图1中的0到1，0到2，0到3，但是它不涉及任意俩点之间的一个距离问题

• 这样就导致我们又研究出一种适合于任意俩点之间距离的一个算法，被我们称为Floyd算法，顾名思义，肯定是弗洛伊德研究出来的嚯嚯嚯

图1

三、算法思想

1、文字解释

弗洛伊德算法首先是构建俩个数组

• $A_v$：初始值为图的邻接矩阵
• $Pat{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];
                }
            }
        }
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

五、视频链接

Floyd算法B站视频链接