图详解第六篇：多源最短路径--Floyd-Warshall算法（完结篇）

2023-10-22 14:31
文章标签 算法 路径 详解 多源 完结篇 floyd 第六篇 warshall

本文主要是介绍图详解第六篇：多源最短路径--Floyd-Warshall算法（完结篇），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

  • 多源最短路径--Floyd-Warshall算法
    • 1. 算法思想
    • 2. dist数组和pPath数组的变化
    • 3. 代码实现
    • 4. 测试观察
    • 5. 源码

前面的两篇文章我们学习了两个求解单源最短路径的算法——Dijkstra算法和Bellman-Ford算法

这两个算法都是用来求解图的单源最短路径的算法，区别在于Dijkstra算法不能求解带负权路径的图，而Bellman-Ford算法可以求解带负权路径的图，当然如果图中存在负权回路（负权环）的情况，种情况是求不出最短路径的！Bellman-Ford算法也无能为力，不过我们可以对负权回路的情况进行判定。

那这篇文章我们要再来学习一个求解多源最短路径的算法——Floyd-Warshall算法

那在前面介绍最短路径的问题的时候就已经给大家解释了什么是单源最短路径，什么是多源最短路径，我们再来回顾一下：

单源最短路径指的是从一个源节点出发，计算到其他所有节点的最短路径。也就是说，在单源最短路径问题中，只需要确定一个起点，然后计算该起点到图中所有其他节点的最短距离。
多源最短路径则是在图中计算任意两个节点之间的最短路径。换言之，需要求解所有可能的起点和终点之间的最短路径。

多源最短路径–Floyd-Warshall算法

Floyd-Warshall算法是一种解决多源最短路径问题（任意两点间的最短路径）的算法。

Floyd算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法（可以求解带负权的图）。
该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。

当然：

我们前面学的Dijkstra算法和Bellman-Ford算法，它们是用来求单源最短路径的，但是我们如果以所有的顶点为起点都走一遍Dijkstra/Bellman-Ford算法的话，其实也可以得到任意两点间的最短距离。
不过呢，Dijkstra算法的话不可以求解带负权路径的图，而Bellman-Ford算法呢效率又有点低。

1. 算法思想

Floyd算法考虑的是一条最短路径的中间节点：

设k是最短路径p的一个中间节点，那么从i到j的最短路径p就被分成i到k和k到j的两段最短路径p1，p2。
p1是从i到k且中间节点属于{1，2，…，k-1}取得的一条最短路径；p2是从k到j且中间节点属于{1，2，…，k-1}取得的一条最短路径
在这里插入图片描述

那它这里如何去求i到j（i，j都可以是任意顶点）最短路径p呢？

在这里插入图片描述
即Floyd算法本质是三维动态规划，D[i][j][k]表示从点i到点j只经过0到k个点最短路径，然后建立起转移方程，然后通过空间优化，优化掉最后一维度，变成一个最短路径的迭代算法，最后即得到所有点的最短路。

给大家简单解释一下上面原理中的这个公式，在动态规划中应该叫状态转移方程：

Di,j,k表示从i到j的最短路径，该路径经过的中间结点是剩余的结点组成的集合中的结点，假设经过k个结点，编号为1…k，然后这里就分为了两种情况：

  1. 如果路径经过了结点k，那么ij的距离就等于ik的距离加上kj的距离，然后剩余就经过k-1个点
  2. 如果不经过结点k，那ij的距离就等于i到j经过k-1个点（不包括k）的距离
    在这里插入图片描述
    那i到j的最短路径就等于这两种情况中的最小值
    在这里插入图片描述

2. dist数组和pPath数组的变化

然后呢在Floyd-Warshall算法中，记录最短路径距离（权值）的dist数组和记录路径（该路径经过了哪些点）的pPath数组我们就要做一些变化了：

前面的两个算法中我们的dist数组和pPath数组都是用了一个一维数组就行了。
但是Floyd-Warshall算法就不一样了，因为前两个算法算的是单源最短路径，而Floyd-Warshall算法是多源最短路径。
因为前面我们都是一个起点，然后求其它顶点到起点的最短路径；而现在是多源，即每个顶点都可以是起点，所以我们要记录每个顶点作为起点时到其它顶点的最短路径距离和路径。
那我们就需要用二维数组了。

3. 代码实现

那下面我们就来尝试写一写Floyd-Warshall算法的代码：

在这里插入图片描述
首先它就不需要给起点了，因为Floyd-Warshall算法求的是多源最短路径，每个顶点都可能是起点，我们都要求
其次，dist数组和pPath数组这里我们要用二维的（vvDist、vvpPath）
然后
在这里插入图片描述
前面的这些初始化工作就不多解释了
接着
我们要把图中所有相连的边的信息直接更新一下，因为上面我们说了那个公式叫做状态转移方程，而这里初始化更新的结果就作为起始状态，后面通过状态转移方程不断更新得到最终结果
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
那然后下面我们就根据状态转移方程更新就行了
在这里插入图片描述

🆗，搞定！

4. 测试观察

那下面我们再加一个打印权值和路径的二维数组的代码，因为上面那个例子也是把每一步对应的两个二维数组（矩阵）画了出来，我们可以打印（每个顶点作为中间结点更新之后的都打印一下）出来观察对比一下：

在这里插入图片描述
这段代码很简单，没什么解释的

然后我们来测试一下：

在这里插入图片描述
这个测试用例就对应上面给大家看的例子中的图
运行一下
在这里插入图片描述
当然我们这里不能像他那样横着打印

我可以给大家调整一下：

在这里插入图片描述
当然我们这里没有打印初始时的状态，所以我们从第二个开始对比。
那大家可以自己对照一下，应该是没问题的

那然后呢我们可以把所有任意两点的最短路径打印一下：

在这里插入图片描述
在这里插入图片描述
任意两点的最短路径都有。
对照一下
在这里插入图片描述
大家可以自己对照看一下，应该没什么问题。

5. 源码

void FloydWarshall(vector<vector<W>>& vvDist, vector<vector<int>>& vvpPath)
{// 初始化一下记录路径和权值（距离）的数组size_t n = _vertexs.size();vvDist.resize(n);vvpPath.resize(n);for (size_t i = 0; i < n; ++i){vvDist[i].resize(n, MAX_W);vvpPath[i].resize(n, -1);}//把图中所有相连的边的信息先更新一下（初始状态）for (size_t i = 0; i < n; i++){for (size_t j = 0; j < n; j++){if (i == j){vvDist[i][j] = W();}if (_matrix[i][j] != MAX_W){vvDist[i][j] = _matrix[i][j];vvpPath[i][j] = i;}}}//按照状态转移方程更新ij的最短路径//依次遍历取图中的每个结点作为ij的中间结点去更新ij的最短路径for (size_t k = 0; k < n; k++){//k作为中间结点更新ij最短路径for (size_t i = 0; i < n; i++){for (size_t j = 0; j < n; j++){if (vvDist[i][k] != MAX_W&& vvDist[k][j] != MAX_W&& vvDist[i][k] + vvDist[k][j] < vvDist[i][j]){vvDist[i][j] = vvDist[i][k] + vvDist[k][j];vvpPath[i][j] = vvpPath[k][j];}}}// 打印权值和路径矩阵观察数据//	for (size_t i = 0; i < n; ++i)//	{//		for (size_t j = 0; j < n; ++j)//		{//			if (vvDist[i][j] == MAX_W)//			{//				//cout << "*" << " ";//				printf("%3c", '*');//			}//			else//			{//				//cout << vvDist[i][j] << " ";//				printf("%3d", vvDist[i][j]);//			}//		}//		cout << endl;//	}//	cout << endl;//	for (size_t i = 0; i < n; ++i)//	{//		for (size_t j = 0; j < n; ++j)//		{//			//cout << vvParentPath[i][j] << " ";//			printf("%3d", vvpPath[i][j]);//		}//		cout << endl;//	}//	cout << "=================================" << endl;}
}

void TestFloydWarShall()
{const char* str = "12345";Graph<char, int, INT_MAX, true> g(str, strlen(str));g.AddEdge('1', '2', 3);g.AddEdge('1', '3', 8);g.AddEdge('1', '5', -4);g.AddEdge('2', '4', 1);g.AddEdge('2', '5', 7);g.AddEdge('3', '2', 4);g.AddEdge('4', '1', 2);g.AddEdge('4', '3', -5);g.AddEdge('5', '4', 6);vector<vector<int>> vvDist;vector<vector<int>> vvpPath;g.FloydWarshall(vvDist, vvpPath);//打印任意两点之间的最短路径for (size_t i = 0; i < strlen(str); ++i){g.ptintMinPath(str[i], vvDist[i], vvpPath[i]);cout << endl;}
}

在这里插入图片描述

这篇关于图详解第六篇：多源最短路径--Floyd-Warshall算法（完结篇）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/262054。

相关文章

MySQL数据库双机热备的配置方法详解

MySQL数据库双机热备的配置方法详解

《MySQL数据库双机热备的配置方法详解》在企业级应用中,数据库的高可用性和数据的安全性是至关重要的,MySQL作为最流行的开源关系型数据库管理系统之一,提供了多种方式来实现高可用性,其中双机热备（M... 目录1. 环境准备1.1 安装mysql1.2 配置MySQL1.2.1 主服务器配置1.2.2 从
阅读更多...
Linux kill正在执行的后台任务 kill进程组使用详解

Linux kill正在执行的后台任务 kill进程组使用详解

《Linuxkill正在执行的后台任务kill进程组使用详解》文章介绍了两个脚本的功能和区别,以及执行这些脚本时遇到的进程管理问题,通过查看进程树、使用`kill`命令和`lsof`命令,分析了子... 目录零. 用到的命令一. 待执行的脚本二. 执行含子进程的脚本，并kill2.1 进程查看2.2 遇到的
阅读更多...
MyBatis常用XML语法详解

MyBatis常用XML语法详解

《MyBatis常用XML语法详解》文章介绍了MyBatis常用XML语法,包括结果映射、查询语句、插入语句、更新语句、删除语句、动态SQL标签以及ehcache.xml文件的使用,感兴趣的朋友跟随小... 目录1、定义结果映射2、查询语句3、插入语句4、更新语句5、删除语句6、动态 SQL 标签7、ehc
阅读更多...
详解SpringBoot+Ehcache使用示例

详解SpringBoot+Ehcache使用示例

《详解SpringBoot+Ehcache使用示例》本文介绍了SpringBoot中配置Ehcache、自定义get/set方式,并实际使用缓存的过程,文中通过示例代码介绍的非常详细,对大家的学习或者... 目录摘要概念内存与磁盘持久化存储：配置灵活性：编码示例引入依赖：配置ehcache.XML文件：配置
阅读更多...
从基础到高级详解Go语言中错误处理的实践指南

从基础到高级详解Go语言中错误处理的实践指南

《从基础到高级详解Go语言中错误处理的实践指南》Go语言采用了一种独特而明确的错误处理哲学,与其他主流编程语言形成鲜明对比,本文将为大家详细介绍Go语言中错误处理详细方法,希望对大家有所帮助... 目录1 Go 错误处理哲学与核心机制1.1 错误接口设计1.2 错误与异常的区别2 错误创建与检查2.1 基础
阅读更多...
k8s按需创建PV和使用PVC详解

k8s按需创建PV和使用PVC详解

《k8s按需创建PV和使用PVC详解》Kubernetes中,PV和PVC用于管理持久存储,StorageClass实现动态PV分配,PVC声明存储需求并绑定PV,通过kubectl验证状态,注意回收... 目录1.按需创建 PV（使用 StorageClass）创建 StorageClass2.创建 PV
阅读更多...
Python版本信息获取方法详解与实战

Python版本信息获取方法详解与实战

《Python版本信息获取方法详解与实战》在Python开发中,获取Python版本号是调试、兼容性检查和版本控制的重要基础操作,本文详细介绍了如何使用sys和platform模块获取Python的主... 目录1. python版本号获取基础2. 使用sys模块获取版本信息2.1 sys模块概述2.1.1
阅读更多...
一文详解Python如何开发游戏

一文详解Python如何开发游戏

《一文详解Python如何开发游戏》Python是一种非常流行的编程语言,也可以用来开发游戏模组,：本文主要介绍Python如何开发游戏的相关资料,文中通过代码介绍的非常详细,需要的朋友可以参考下... 目录一、python简介二、Python 开发 2D 游戏的优劣势优势缺点三、Python 开发 3D
阅读更多...
Redis 基本数据类型和使用详解

Redis 基本数据类型和使用详解

《Redis基本数据类型和使用详解》String是Redis最基本的数据类型,一个键对应一个值,它的功能十分强大,可以存储字符串、整数、浮点数等多种数据格式,本文给大家介绍Redis基本数据类型和... 目录一、Redis 入门介绍二、Redis 的五大基本数据类型2.1 String 类型2.2 Hash
阅读更多...
Java中的.close()举例详解

Java中的.close()举例详解

《Java中的.close()举例详解》.close()方法只适用于通过window.open()打开的弹出窗口,对于浏览器的主窗口,如果没有得到用户允许是不能关闭的,：本文主要介绍Java中的.... 目录当你遇到以下三种情况时，一定要记得使用 .close()：用法作用举例如何判断代码中的 input
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2