数据结构＜图＞Floyd算法(这次无代码，加入一个算法的实现流程思路)

图结构-----Floyd算法

1、前言

根据计算机考研中对于求解最短路径算法的出题形式&＃xff0c;以Dijkstra算法为重要考点&＃xff0c;Dijkstra算法对于求解一个顶点到其他任意的顶点之间的最短路径的问题&＃xff0c;可以说是非常实用。
同时对于求解各个端点到其他端点的最短路径的集合这个问题&＃xff0c;Dijkstra算法便没有那么优势了&＃xff0c;本着学习就要学全面的特点&＃xff0c;下面对Floyd算法进行原理讲解&＃xff0c;(只讲执行过程&＃xff0c;不涉及到算法的代码实现)

2、算法介绍

时间复杂度介绍

1. 相比于Dijkstra算法&＃xff0c;Floyd算法的时间复杂度是非常高的。
2. 时间复杂度为O(n3)&＃xff0c;(n的三次方)&＃xff0c;其时间复杂度是非常的高。

算法执行准备

1. 首先给出要讲解的题目例子图如下&＃xff1a;

2. Floyd算法的执行过程需要我们在草稿纸上画出&＃xff0c;两个矩阵&＃xff0c;一个是上图中的边与边对应的权值关系&＃xff0c;另一个是节点指向节点的路径显示&＃xff0c;因此给出两个矩阵结构图如下&＃xff1a;

3. 准备好初始的矩阵的条件节点后&＃xff0c;我们对其进行Floyd算法的执行分析&＃xff1a;

Floyd算法执行过程

1. 首先是选取第二个矩阵中的初始路径&＃xff0c;这里以第一行中的A->B为开始操作路径。
2. Floyd算法第一步---------在A->B选择路径后&＃xff0c;加入节点C&＃xff0c;对其当前的矩阵中的所有节点进行路径的更新
3. 更新的原则&＃xff1a;若加入了C&＃xff0c;使得其中的一个路径长度变短&＃xff0c;便更新&＃xff0c;否则不更新。
4. 其第一轮更新过程图如下&＃xff1a;

根据上述图片对其进行第一轮的加入C节点进行操作分析&＃xff1a;

1. 找到不带C节点的路径&＃xff0c;对于当前的路径长度跟加入C节点后的路径长度进行对比
2. 若小于当前的路径长度&＃xff0c;则更新该位置
3. 若不小于则保持原型

下面进行第二轮更新&＃xff0c;选择加入B节点&＃xff1a;其执行图如下&＃xff1a;

以上是第二轮加入B节点进行矩阵更新后的第二轮流程&＃xff1a;

最后是最后一轮加入节点A&＃xff0c;由于其中一共有三个节点&＃xff0c;因此只需要执行三轮&＃xff0c;这里有几个节点就要几轮操作。

第三轮更新&＃xff1a;加入A节点
执行图如下&＃xff1a;

其Floyd执行算法的流程如下&＃xff0c;其思路了解掌握就好&＃xff0c;代码时间复杂度n的三次方有点高&＃xff0c;有需要可以了解下。