多源最短路径算法:Floyd-Warshall算法分析

在这里插入图片描述

文章目录

    • 图的邻接矩阵
  • 一.Floyd-Warshall算法思想(基于动态规划)
  • 二.Floyd-Warshall算法接口
  • 笔记附录:单源最短路径--Bellman-Ford算法
    • 1.Bellman-Ford算法接口核心部分
    • 2.Bellman-Ford算法接口

图的邻接矩阵

namespace Graph_Structure
{//Vertex是代表顶点的数据类型,Weight是边的权值的数据类型,MAX_W是权值的上限值(表示不相两)//Direction表示图是否为有向图template<class Vertex, class Weight = int, Weight MAX_W = INT_MAX, bool Direction = false>class Graph{typedef Graph<Vertex, Weight, MAX_W, Direction> Self;public://使用编译器的默认构造函数Graph() = default;//给定一个存放顶点的数组用来初始化图Graph(const Vertex* a, size_t n){_vertexs.reserve(n);_indexMap.rehash(n);_matrix.resize(n, std::vector<Weight>(n, MAX_W));for (size_t i = 0; i < n; ++i){_vertexs.push_back(a[i]);//建立顶点和数组下标的映射(目的是为了邻接矩阵的边存储)_indexMap[a[i]] = i;}}//获取顶点在邻接矩阵中对应的下标size_t GetVertexIndex(const Vertex& vertex){if (_indexMap.find(vertex) == _indexMap.end()){throw "invalued_para";return -1;}return _indexMap[vertex];}void _AddEdge(size_t srci, size_t dsti, const Weight& w){//判断是有向图还是无向图if (Direction == false){_matrix[dsti][srci] = w;}_matrix[srci][dsti] = w;}//给定起点和终点,在邻接矩阵中添加一条边void AddEdge(const Vertex& src, const Vertex& dst, const Weight& w){if (_indexMap.find(src) == _indexMap.end() || _indexMap.find(dst) == _indexMap.end()){throw "invalued_para";}size_t srci_index = GetVertexIndex(src);size_t dst_index = GetVertexIndex(dst);_AddEdge(srci_index, dst_index, w);}//将图的邻接矩阵打印出来void Print(){for (auto e : _vertexs){std::cout << e << '[' << _indexMap[e] << ']' << std::endl;}std::cout << "     ";for (int i = 0; i < _vertexs.size(); ++i){std::cout << i << "    ";}std::cout << std::endl;int i = 0;for (auto arry : _matrix){std::cout << i++ << ' ';for (auto e : arry){if (e == MAX_W){printf("%4c ", '*');}else{printf("%4d ", e);}}std::cout << std::endl;}}//图的广度优先遍历void BFS(const Vertex& src){size_t begin = GetVertexIndex(src);std::queue<int> QNode;std::vector<bool> Label(_vertexs.size(), false);QNode.push(begin);Label[begin] = true;size_t Level = 0;while (!QNode.empty()){size_t LevelSize = QNode.size();for (size_t i = 0; i < LevelSize; ++i){size_t front = QNode.front();QNode.pop();std::cout << _vertexs[front] << '[' << front << ']' << std::endl;for (int j = 0; j < _vertexs.size(); ++j){if (Label[j] == false && _matrix[front][j] != MAX_W){QNode.push(j);Label[j] = true;}}}}}//图的深度优先遍历void DFS(const Vertex& src){std::vector<bool> visited(_vertexs.size(), false);_DFS(GetVertexIndex(src), visited);}private:void _DFS(size_t srci, std::vector<bool>& visited){visited[srci] = true;std::cout << _vertexs[srci] << '[' << srci << ']' << std::endl;for (int i = 0; i < _vertexs.size(); ++i){if (_matrix[srci][i] != MAX_W && visited[i] == false){_DFS(i, visited);}}}private:std::vector<Vertex> _vertexs;						// 顶点集合std::unordered_map<Vertex, size_t> _indexMap;		// 顶点映射下标std::vector<std::vector<Weight>> _matrix;			// 邻接矩阵};
}

在有向赋权图中(可以存在带负权值的路径,但不能存在总权值为负数的环路),Floyd-Warshall算法可以求出任意两个顶点间的最短路径

一.Floyd-Warshall算法思想(基于动态规划)

  • 假设图中有N个顶点,顶点按照0~N-1进行编号

  • 算法中使用二维数组Dist来记录点与点之间的最短路径长度,Dist[i][j]表示第i个顶点到第j个顶点的最短路径长度,Dist数组的初始状态图的邻接矩阵的拷贝

  • 任意两个顶点ij之间的最短路径上可能存在0 ~ N-2个顶点:在这里插入图片描述

  • 假设顶点i到顶点j的最短路径上编号最大的顶点k顶点,ik之间的路径为p1,kj之间的路径为p2(不难证明,p1同时也是顶点i到顶点k的最短路径,p2同时也是顶点k到顶点j的最短路径)

  • 从而有状态转移方程: Dist[i][j] = Dist[i][k] + Dist[k][j]在这里插入图片描述

  • 最短路径p1p2也可以按照相同的方式划分出子路径.重复路径划分,直到将路径划分成不能再被分割的各个最小状态,从各个最小状态开始进行状态转移就可以得到顶点i到顶点j的最短路径.

  • 状态转移任意两点的最短路径的过程可以通过如下循环完成:

			//动态规划求最优解for (int k = 0; k < _vertexs.size(); ++k){for (int i = 0; i < _vertexs.size(); ++i){for (int j = 0; j < _vertexs.size(); ++j){if (Dist[i][k] != MAX_W && Dist[k][j] != MAX_W &&Dist[i][k] + Dist[k][j] < Dist[i][j]){Dist[i][j] = Dist[i][k] + Dist[k][j];}}}}

在这里插入图片描述

  • 其他任意两点的最短路径的确定过程也是类似的

二.Floyd-Warshall算法接口

		//多源最短路径算法(允许带负权路径存在)//Dist数组用于记录顶点间的最短路径的长度//ParentPath数组用于记录最短路径上某个顶点的前驱结点编号void FloydWarShall(std::vector<std::vector<Weight>>& Dist, std::vector<std::vector<int>>& ParentPath){Dist.resize(_vertexs.size(), std::vector<Weight>(_vertexs.size(), MAX_W));ParentPath.resize(_vertexs.size(), std::vector<int>(_vertexs.size(), -1));//根据图的邻接矩阵初始化Dist数组for (int i = 0; i < _matrix.size(); ++i){for (int j = 0; j < _matrix.size(); ++j){if (i == j){Dist[i][j] = 0;}else if(_matrix[i][j] != MAX_W){Dist[i][j] = _matrix[i][j];ParentPath[i][j] = i;}}}//动态规划求各个最短路径for (int k = 0; k < _vertexs.size(); ++k){for (int i = 0; i < _vertexs.size(); ++i){for (int j = 0; j < _vertexs.size(); ++j){if (Dist[i][k] != MAX_W && Dist[k][j] != MAX_W &&Dist[i][k] + Dist[k][j] < Dist[i][j]){Dist[i][j] = Dist[i][k] + Dist[k][j];//i到j最短路径上,j顶点的前驱为k到j最短路径上j的前驱ParentPath[i][j] = ParentPath[k][j];}}}}}

笔记附录:单源最短路径–Bellman-Ford算法

  • Bellman-Ford算法可以在带负权路径的图中求解单源最短路径的问题
  • 一维数组Dist用于记录源点到其他顶点的最短路径的长度:Dist[i]表示源点到i号结点的最短路径长度
  • 一维数组ParentPath数组用于记录最短路径上某个顶点的前驱结点编号:ParentPath[i]表示在最短路径上,第i号结点的前驱结点的编号

1.Bellman-Ford算法接口核心部分

			for (int i = 0; i < _vertexs.size() - 1; ++i){for (int j = 0; j < _vertexs.size(); ++j){for (int k = 0; k < _vertexs.size(); ++k){if (_matrix[j][k] != MAX_W && dist[j] != MAX_W &&_matrix[j][k] + dist[j] < dist[k]){dist[k] = _matrix[j][k] + dist[j];parentPath[k] = j;}}}
  • 可以证明:上面的循环可以遍历任何一条可能存在的最短路径.对于任意一条最短路径,内部的双层循环至少可以记录下最短路径上的一条边,因此最外层循环只要进行N-1次(N为图的顶点数目)就可以遍历完所有的最短路径:在这里插入图片描述
  • Bellman-Ford算法需要检验图中是否存在总权值为负数的环路,存在总权值为负数的环路的图无法求解最短路径问题

2.Bellman-Ford算法接口

		//带负权路径的单源最短路径算法bool BellmanFord(const Vertex& src, std::vector<Weight>& dist, std::vector<int>& parentPath){dist.resize(_vertexs.size(), MAX_W);parentPath.resize(_vertexs.size(), -1);int srci = GetVertexIndex(src);dist[srci] = Weight();bool flag = true;for (int i = 0; i < _vertexs.size() - 1; ++i){for (int j = 0; j < _vertexs.size(); ++j){for (int k = 0; k < _vertexs.size(); ++k){if (_matrix[j][k] != MAX_W && dist[j] != MAX_W &&_matrix[j][k] + dist[j] < dist[k]){//经过j结点,更新源点到k结点的路径长度dist[k] = _matrix[j][k] + dist[j];parentPath[k] = j;flag = false;}}}if (flag){//路径不再发生更新,则说明所有最短路径都已经确定return false;}flag = true;}//检验图中是否存在负权环路//如果存在负权环路,则Dist数组会继续被更新flag = false;for (int j = 0; j < _vertexs.size(); ++j){for (int k = 0; k < _vertexs.size(); ++k){if (_matrix[j][k] != MAX_W && dist[j] != MAX_W &&_matrix[j][k] + dist[j] < dist[k]){dist[k] = _matrix[j][k] + dist[j];flag = true;}}}return flag;}

在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/116382.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Approaching (Almost) Any Machine Learning Problem中译版

前言 Abhishek Thakur&#xff0c;很多kaggler对他都非常熟悉&#xff0c;2017年&#xff0c;他在 Linkedin 发表了一篇名为Approaching (Almost) Any Machine Learning Problem的文章&#xff0c;介绍他建立的一个自动的机器学习框架&#xff0c;几乎可以解决任何机器学习问题…

JY901B智能9轴加速度计陀螺仪角度传感器

今日学习使用JY901B智能9轴加速度计陀螺仪角度传感器 本文会先使用上位机获取数据作演示&#xff0c;后介绍它的数据表发送原理。 文章提供详细的原理讲解&#xff0c;测试工程下载&#xff0c;代码讲解&#xff0c;本人有多注释的习惯&#xff0c;希望对大家有帮助。 我的J…

【LeetCode】剑指 Offer <二刷>(4)

目录 题目&#xff1a;剑指 Offer 09. 用两个栈实现队列 - 力扣&#xff08;LeetCode&#xff09; 题目的接口&#xff1a; 解题思路&#xff1a; 代码&#xff1a; 过啦&#xff01;&#xff01;&#xff01; 题目&#xff1a;剑指 Offer 10- I. 斐波那契数列 - 力扣&am…

FFmpeg5.0源码阅读——FFmpeg大体框架

摘要&#xff1a;前一段时间熟悉了下FFmpeg主流程源码实现&#xff0c;对FFmpeg的整体框架有了个大概的认识&#xff0c;因此在此做一个笔记&#xff0c;希望以比较容易理解的文字描述FFmpeg本身的结构&#xff0c;加深对FFmpeg的框架进行梳理加深理解&#xff0c;如果文章中有…

Linux 常见命令操作

一、目录管理 1.1 列出目录 ls # ls 命令 # -a 参数&#xff0c;查看全部的文件&#xff0c;包括隐藏的文件 # -l 参数&#xff0c;列出所有的文件&#xff0c;包括文件的属性和权限&#xff0c;不显示隐藏文件 [rootlocalhost /]# ls bin boot dev etc home lib lib64…

C# Dapper 操作Oracle数据库

nuget安装内容 1.配置连接字符串 OracleConnectionString这个可用 {"Logging": {"LogLevel": {"Default": "Information","Microsoft.AspNetCore": "Warning"}},"AllowedHosts": "*","…

前几天写的博客被选中进入【CSDN月度精选】榜单

小收获&#xff0c;记录一下&#xff0c;哈哈 这个貌似是CSDN给的排名和得分&#xff1a;

中东 Shopify 如何使用 Bytebase 构建一站式数据库开发工作流

公司简介 Salla 是一家 2016 年成立&#xff0c;位于沙特麦加的自建站电商平台。 作为中东 Shopify&#xff0c;其最大的特点是支持阿拉伯语建站&#xff0c;并且提供更多适应中东地区特点的本地化服务。截止目前&#xff0c;已有 47,000 家店铺入驻 Salla&#xff0c;商品销售…

云计算环境中高性能计算的挑战与对策

文章目录 云计算中的高性能计算挑战1. 资源竞争&#xff1a;2. 网络延迟&#xff1a;3. 数据传输效率&#xff1a;4. 虚拟化开销&#xff1a;5. 节点异构性&#xff1a; 高性能计算在云计算环境中的对策1. 定制化虚拟机镜像&#xff1a;2. 弹性资源调整&#xff1a;3. 高效数据…

springCloud整合Zookeeper的时候调用找不到服务

SpringCloud整合Zookeeper的时候调用找不到服务 首先&#xff0c;我们在注册中心注册了这个服务&#xff1a; 然后我们使用RestTemplate 调用的时候发现失败了&#xff1a;找不到这个服务&#xff1a; 找了很多资料发现这个必须要加上负载才行 BeanLoadBalanced //负载publi…

_数字矩阵

题目&#xff1a;一个3阶的数字矩阵如下&#xff1a; 1 2 3 8 9 4 7 6 5 现在给定数字n(1<n≤20)&#xff0c;输出n阶数字矩阵。 思路&#xff1a; 放出一条好玩的贪吃蛇&#xff0c;按照右下左上的顺序吃蛋糕&#xff0c;一边吃蛋糕&#xff0c;一边拉数字&#xff1b…

高级IO(select、poll、epoll)

在介绍本文之前&#xff0c;先提出一个问题 什么是IO&#xff1f; 等数据拷贝 1.等 - IO事件就绪&#xff08;检测功能成分&#xff09; 2.数据拷贝 高效的IO就是&#xff1a;单位时间&#xff0c;等的比重越小&#xff0c;IO的效率越高 五种IO模型 IO模型&#xff1a; 阻塞式…

微服务通信[HTTP|RPC同步通信、MQ异步通信]

概念 A服务调用B服务,B服务调C服务,C服务调D服务,即微服务之间的通信(也可以叫微服务之间的调用) HTTP同步通信 一种轻量级的通信协议,常用于在不同的微服务之间进行通信,也是最简单的通信方式使用REST ful为开发规范&#xff0c;将服务对外暴露的HTTP调用方式为REST API(如GET…

ChatGPT 实现动态地图可视化展示

地图可视化分析有许多优点和好处: 1.直观理解:地图可视化使得复杂的数据更易于理解。通过地图可视化,人们可以直观地看到地理位置、地区之间的关系以及空间分布的模式。 2.提高决策效率:地图可视化可以帮助决策者快速理解和解释数据,从而提高决策效率。 3.高效的数据整…

Redis 哨兵(sentinel)

1. 是什么一 1.1 吹哨人巡查监控后台master主机是否故障&#xff0c;如果故障了根据投票数自动将某一个从库转换为新主库&#xff0c;继续对外服务 1.2 作用 俗称&#xff0c;无人值守运维 哨兵的作用&#xff1a; 1、监控redis运行状态&#xff0c;包括master和slave 2、当m…

leetcode 1326. Minimum Number of Taps to Open to Water a Garden

x轴上的花园范围为[0,n], 0~n这个n1个离散点上有水龙头&#xff0c;第 i 个水龙头能浇水的范围为[i-ranges[i], iranges[i]]. 求能浇整个花园的最小水龙头个数。 思路&#xff1a; 方法一&#xff1a; greedy 先把每个水龙头能浇的区间准备好&#xff0c; 用一个数组保存所有…

C盘扩容遇到的问题(BitLocker解密、)

120G的C盘不知不觉的就满了&#xff0c;忍了好久终于要动手了。 尽管电脑-管理--磁盘管理里可以进行磁盘大小调整&#xff0c;但由于各盘都在用&#xff0c;不能够连续调整&#xff0c;所以选用DiskGenius。 # DiskGenius调整分区大小遇到“您选择的分区不支持无损调整容量” …

stable diffusion实践操作-提示词

系列文章目录 stable diffusion实践操作 文章目录 系列文章目录前言一、提示词是什么&#xff1f;1.1、提示词的原理 二、使用步骤2.1 核心原则2.2、提示词分类2.2.1 正向提示词2.2.2 反向提示词 2.3、提示词书写模板2.3.1 画质&#xff1a;2.3.2. 主体结构2.3.3. 主体细节2.3…

Ubuntu 20.04 Server配置网络

0&#xff0c;环境 服务器&#xff1a; Intel(R) Xeon(R) Gold 6248R CPU 3.00GHz 96核 网卡&#xff1a; 多网卡 1&#xff0c; 镜像下载 http://old-releases.ubuntu.com/releases/ubuntu-20.04.1-desktop-amd64.iso 2&#xff0c; 系统安装--具体步骤就不贴出来&#…

Python基础之基础语法(二)

Python基础之基础语法(二) 语言类型 静态语言 如&#xff1a;C C Java ina a 100 a 100 a abc # 不可以静态语言需要指定声明标识符的类型&#xff0c;之后不可以改变类型赋值。静态语言变异的时候要检查类型&#xff0c;编写源代码&#xff0c;编译时检查错误。 动态语…