Floyd算法(弗洛伊德)基本实现以及代码

  • Post author:
  • Post category:其他




一、本文的由来

数据结构老师布置了一个题目,要求我们写Floyd算法的实现过程的PPT(我不理解,孩子又不是教技的娃娃,为啥还要讲课做PPT嘞)

好吧~为了上课cue到我的时候,不会被发现我在摸鱼,我还是康了康视频,后面会把视频链接附在最后,有兴趣的同学可以康康



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

  • Floyd的算法由来,应该是在

    迪杰斯特拉算法的基础

    之上,对图的最短路径的一个更深的理解。

  • 迪杰斯特拉算法主要是对于俩点之间的距离,比如

    图1

    中的0到1,0到2,0到3,但是它不涉及任意俩点之间的一个距离问题

  • 这样就导致我们又研究出一种适合于

    任意俩点之间距离

    的一个算法,被我们称为

    Floyd算法

    ,顾名思义,肯定是弗洛伊德研究出来的嚯嚯嚯

图1
在这里插入图片描述



三、算法思想



1、文字解释

弗洛伊德算法首先是

构建俩个数组




  • A

    v

    A_v







    A










    v





















    :初始值为图的邻接矩阵




  • P

    a

    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];
                }
            }
        }
    }



五、视频链接


Floyd算法B站视频链接



版权声明:本文为weixin_42198265原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。