-
Floyd算法求解多元最短路径问题
2020-08-27 21:44:44Floyd算法求解多元最短路径问题 ** 问题描述: 对于多个目标地A,B,C…,求解两地之间的最短路径问题,例如求解 A-C的距离,常见的解有两种,一种是直接由A-C,另一种是经过某个中转地再到达目的地,即A-B-C,其中...**
Floyd算法求解多元最短路径问题
**
问题描述:
对于多个目标地A,B,C…,求解两地之间的最短路径问题,例如求解 A-C的距离,常见的解有两种,一种是直接由A-C,另一种是经过某个中转地再到达目的地,即A-B-C,其中中转地可以是n个。floyd算法解释:
floyd算法的核心思想是将多地间的距离构建为一个距离矩阵(即二维数组),然后再通过遍历方法,刷新距离矩阵,下面通过一组实例来解释:
例如有A,B,C,D四个目标地点,其相互间的距离为矩阵中所示,
其中4行1列的“7”,与1行4列的“7”,均表示由A-D的距离为7,但是我们发现,若需要从A地去D地,若途径C地,需要“1”步,再由C去D,需要“5”步,则采用A-C-D的路线,共需要“6”步,最短路径的问题从而产生。所以算法的思想就是,遍历找到合适的中转点,使得由出发地去目的地的路程最短。算法实现:
step1、建立原始距离矩阵:int map[4][4] = { 0,4,1,7, 4,0,2,3, 1,2,0,5, 7,3,5,0 };
step2、floyd遍历实现:
for(mid = 0 ; mid < 4 ; mid++) { for(start = 0 ; start < 4 ; start ++) { for(end = 0 ;end<4 ; end ++) { if((start == end)||(start == mid)||(end == mid)) continue ; if(map[start][mid] + map[mid][end] <map[start][end]) { map[start][end]= map[start][mid] + map[mid][end] ; } } } }
step3、输出最短距离矩阵:
完整的代码为:
#include <iostream> using namespace std ; int main() { int map[4][4] = { 0,4,1,7, 4,0,2,3, 1,2,0,5, 7,3,5,0 }; cout<<"before floyd"<<endl ; for(int i = 0 ; i < 4 ; i++) { for(int j = 0 ; j < 4 ; j ++) { cout<<map[i][j]<<" " ; } cout<<endl ; } cout<<"after floyd"<<endl ; int mid = 0 ; int start = 0 ; int end = 0 ; for(mid = 0 ; mid < 4 ; mid++) { for(start = 0 ; start < 4 ; start ++) { for(end = 0 ;end<4 ; end ++) { if((start == end)||(start == mid)||(end == mid)) continue ; if(map[start][mid] + map[mid][end] <map[start][end]) { map[start][end]= map[start][mid] + map[mid][end] ; } } } } for(int i = 0 ; i < 4 ; i++) { for(int j = 0 ; j < 4 ; j ++) { cout<<map[i][j]<<" " ; } cout<<endl ; } system("pause"); return 0 ; }
测试输出结果:
floyd的核心代码其实就是循环遍历的那几行,找到合适的中转点,使得从起始地至目的地的距离最短,适合求解多源最短路径问题,欢迎大家交流。 -
多元最短路径——Floyd-Warshall算法
2018-09-09 22:00:40多源最短路径——Floyd-Warshall算法 首先分析这张图 就拿从1到3,可以直接1->3,也可以1->2->3,我们发现,通过一个“中转”的2,1->3路径会变短。 可以在一个路径中插入另一个...多源最短路径——Floyd-Warshall算法
首先分析这张图
就拿从1到3,可以直接1->3,也可以1->2->3,我们发现,通过一个“中转”的2,1->3路径会变短。
可以在一个路径中插入另一个顶点,这样可能会比直接过去的路径更短,假设每个顶点都经过顶点2中转,可以有这样的语句。
我们用二维数组graph[][]存储图
int i; int j; for(i=1;i<=n;++i){ for(j=1;j<=n;++j){ if(graph[i][j]>graph[i][2]+graph[2][j])//通过中转路径变短了 graph[i][j]=graph[i][2]+graph[2][j];//则将从i到j的路径长度改为中转后的较短路径 } }
中转顶点可以是图中的任意一个顶点,所以将所有顶点做一次中转顶点 即可以将用一个循环变量来当作中转点
int i; int j; int k; for(k=1;k<=n;++k){ for(i=1;i<=n;++i){ for(j=1;j<=n;++j){ if(graph[i][j]>graph[i][2]+graph[2][j])//通过中转路径变短了 graph[i][j]=graph[i][2]+graph[2][j];//则将从i到j的路径长度改为中转后的较短路径 } } }
完整代码如下:
#include <stdio.h> const int INF=999999999; int main(void){ int graph[10][10]; int n,m;//n个顶点,m条边 printf("请输入定点数与边数:"); scanf("%d%d",&n,&m); //初始化二维数组 for(int i=1;i<=n;++i){ for(int j=1;j<=n;++j){ graph[i][j]=INF; } graph[i][i]=0; } for(int i=1;i<=m;++i){ int s,e; printf("第%d条边及其权值:",i ); scanf("%d%d",&s,&e); scanf("%d",&graph[s][e]); } /*********核心部分*********/ int i,j,k; for(i=1;i<=n;++i) for(j=1;j<=n;++j) for(k=1;k<=n;++k){ if(graph[j][i]!=INF && graph[i][k]!=INF && graph[j][i]+graph[i][k]<graph[j][k]) graph[j][k]=graph[j][i]+graph[i][k]; } /*************************/ printf("\n===========================\n"); for(i=1;i<=n;++i) for(j=1;j<=n;++j){ if(graph[i][j]!=INF && graph[i][j]) printf("%d-->%d %d\n",i,j,graph[i][j]); } return 0; }
虽然用插一个中转点来引出这段代码,但是最短路径不一定全是只会有一个中转点。
举个栗子:假设一个最短路径是1->3->5->7,上述算法先找出从1到5的最短路径是1->3->5,现在的graph[1][5]被更新成为了grap[1][3]+graph[3][5],接下来计算1->7的最短路径时上述算法算出的时1->5->7,这里的1->5实际上是1->3->5。这样说可能有点乱,希望的对理解这个算法有点帮助。
-
基于多元信息评估的矿井火灾救援路径优化
2020-05-08 06:14:41针对目前煤矿井下火灾救援模型过于复杂、对巷道安全因子的研究不够深入、未考虑灾后巷道交通网络连通度的问题,建立了基于多元信息评估的矿井火灾救援路径优化模型。对火灾后巷道内温度、瓦斯浓度、烟雾能见度等环境... -
ArcGIS计算城市间最短距离(多元最短路径)
2020-07-27 19:52:24最短路径1. 准备工作数据准备(以湖北省为例)环境2. 步骤2.1 截取湖北省数据2.1.1 新建地图(多源最短路径-湖北)2.1.2 内容列表窗口>>图层>>右键>>添加数据, 再全国行政区划分中导入省和市的...目录
0. 最短路径
- 数据结构中,图的相关知识中的一个重要知识点就是计算最短路径的问题。期中包括两个解决办法:
- 单源最短路径: Dijkstra算法.
- 多源最短路径:Floyd算法.
- 问题:使用上述算法计算出来的最短路径长度,一般属于直线距离,如果用于计算城市间的最短距离,则不符合实际情况。
- 城市间的各种联系往往基于路网发生,因此我们需要使用路网的距离作为两个城市间的实际距离。
ArcGIS中提供了计算路网距离的方法,现以湖北省为例,使用ArcGIS计算各地级市之间的最短距离。
1. 准备工作
数据准备(以湖北省为例)
- 准备湖北省边界、湖北各个市的边界和地级市驻点数据
- 准备路网数据(国道、省道)
链接:https://pan.baidu.com/s/1GVGuVsl-iEhqN25XiD9eVw 提取码:gi7h
环境
- ArcGIS 10.2
- 激活网络分析模块
- 菜单 >> 自定义 >> 扩展模块 >> 勾选Network Analyst
Customer >> Extensions >> Network Analyst
- 菜单 >> 自定义 >> 扩展模块 >> 勾选Network Analyst
- 加载网络分析工具条
- 工具栏空白处 >> 右键 >> 选择: Network Analyst
- 工具栏空白处 >> 右键 >> 选择: Network Analyst
2. 步骤
2.1 截取湖北省数据
2.1.1 新建地图(多源最短路径-湖北)
2.1.2 内容列表窗口>>图层>>右键>>添加数据, 再全国行政区划分中导入省和市的矢量图
2.1.3 对图层中的省点击右键>>打开属性表
全国各省列表, 名字乱码了, 按照邮编找>> 选择420000这一行(湖北省)
2.1.4 导出湖北省的边界
右键点击"省"图层>>数据>>导出数据
导出: 所选要素 >> 输出要素类: 找到保存位置, shapfile类型文件, 命名 >> 确定
将导出数据添加道图层中: 是 >> 删除原省份图层
2.1.5 导出地级市边界
"市"图层 >> 右键 >> 打开属性表 >> 选择多行(邮编420000,第三列)
“市"图层 >> 右键 >> 数据 >> 导出数据 >> 保存到"湖北省-市界.shp"中 >> 在图层中显示 >> 删除原"市图层”
2.2 创建网络数据集
2.2.1 创建文件数据库
- 界面右侧 >> 目录工具栏 >> 右键 >> 新建 >> 文件夹 >> 文件数据库
- 文件数据库 >> 右键 >> 新建 >> 文件地理数据数据 >> 湖北-交通
- 湖北-交通.gdb >> 右键 >> 新建 >> 要素数据集 >> 名称: 路网 >> 坐标系: WGS 1984 >> … >> 完成
2.2.2 导入要素类
路网 >> 右键 >> 导入 >> 要素类(单个) >> 输入要素: 选择湖北省国道中的.shp文件 >> 输出要素类: 国道 >> 确定
再导入省道的数据 >> 同意添加道图层
2.2.3 创建网络数据集
路网 >> 右键 >> 新建 >> 网络数据集(N) >> 命名: 网络_ND >> 勾选国道和省道 >>> 下一步 >>> 完成 >> 立即构建 >> 添加到地图
2.3 计算城市间网络距离
2.3.1 打开网络分析窗口
2.3.2 创建OD成本矩阵
左侧显示网络分析窗口
2.3.3 添加起始点和目的地点
a) 在内容列表中加入地级市的驻点, 作为参考确定起始点, 仅留下"地级市"和"路网_ND"两个图层.
b) 在网络分析工具栏上选择创建网络位置工具
c) 网络分析窗口中选择起始点, 用鼠标点击地级市的位置, 添加18个点
d) 给这18个点矫正位置, 并重新命名
内容列表 >> “地级市"图层 >> 右键 >> 打开属性表
选择第一行, 图层上相应的点会高亮
在网络分析工具栏上点击"选择/移动网络位置"按钮
选择图层上刚才高亮显示的城市点, 在网络分析窗口中的起始点列表会高亮显示
双击修改其名字为"鄂州市” >> 确定
右键点击鄂州市 >> 缩放至所选要素
找到该点所在位置 >> 选择该点 >> 按住键盘上的"1" >> 将其托到附近的线上
完成18个地级市的起始点创建
e) 增加目的地, 我们要计算的是多源最短路径, 所以起始点也是终点, 将上面的18个点全选, 按住ctrl拖到目的地点中, 增加18个目的地点.
2.3.4 生成OD 成本矩阵
点击网络分析工具栏中的求解
会生成18*18 = 324条最短路径的线
这显然不是我们想要的表现形式. 我们先在内容列表上把OD成本矩阵的图层取消, 下一步我们进行OD成本矩阵的可视化展示.2.3.5 导出OD成本矩阵
- 打开ArcToolbox
选择里面的转换工具>> Excel >> 表转Excel
在输入表的下拉列表中选择OD成本矩阵中的线 >> 选择输出文件的路径和名字>> 点击确定
期中 Tota_长度, 为两个城市间最短路径的长度(单位: 米).
2.4 可视化
2.4.1 生成城市点对
想要画出路径图, 需要知道路径的起点和终点
- 导出路径的起点, 使用要素折点转点工具, ArcToolbox >> 数据管理工具 >> 要素 >> 要素折点转点工具.
选取输入要素下拉列表中OD成本矩阵下的"线" >> 点类型选择START >> 确定
- 导出路径的终点
选取输入要素下拉列表中OD成本矩阵下的"线" >> 点类型选择END >> 确定
内容中增加了如下内容
2.4.2 新建路径
- 选择网络分析中的新建路径
网络分析窗口中增加了路径窗口
- 增加停靠点
右键点击停靠点 >> 加载位置
增加起点: 加载自下拉列表中选择,刚才添加的START的要素 >> name字段设为空 >> RouteName字段设为 name
增加终点: 加载自下拉列表中选择,刚才添加的END的要素 >> name字段设为空 >> RouteName字段设为 name
增加了324条路径的648个停靠点
2.4.3 生成路径
点击Network工具栏上的求解.生成路径
生成并显示了324条最短路径
3 收尾
加上省界和市界的图层, 生成最终效果图
编辑后的数据下载
- 数据结构中,图的相关知识中的一个重要知识点就是计算最短路径的问题。期中包括两个解决办法:
-
煤炭企业股权多元化改革的有效实施路径
2020-06-16 06:04:18基于理论回顾与案例分析,探讨煤炭企业股权多元化改革的有效实施路径,主要包括引入非国有资本参与国有企业改革、向发展潜力大和成长性好的非国有企业进行股权投资、实施员工持股计划、登陆资本市场并引进机构投资者。 -
绘制贝塞尔路径点, 多元贝塞尔路线并且导出所有路径点至json或者text文件。
2018-07-11 11:32:21 -
挑战程序设计(算法和数据结构)—图论(最小生成树、单源最短路径和多元最短路径、拓扑排序)
2019-02-14 19:13:12单源最短路径 使用Bellman-Ford算法 SFPA算法(Bellman-Ford算法的改进) 使用dijstra算法 多源最短路径和拓扑排序 最小生成树 题目13.2链接 Minimum Spanning Tree 采用Prim算法 二者均采用邻接矩阵 第一... -
多元统计分析最短距离法_漫画:数据结构之最短路径 Dijkstra 算法的优化
2020-12-28 11:52:05在《漫画:图的 “最短路径” 问题》一文中小灰介绍了单源最短路径算法 Dijkstra。当时漫画中我们遗留了一个问题:如何求得最短路径的详细节点,而不仅仅是距离?——在本篇中,我们将会给与解答。我们仍然以下面这... -
论文研究 - 使用多元分析评估发展中国家在1995-2010年期间的发展路径趋势
2020-05-29 15:48:34国别发展是一个复杂的问题,从严格的经济观点到更综合的愿景都可以指代。 这项研究从获得基本服务,水资源管理和捐助者的外部支持等方面分析了可持续发展。 根据22个变量对103个国家进行了分析,这些变量包括获得... -
ac之迪杰斯特拉--单源到多元最短路径--正权值---O(v^2)算法
2018-04-10 20:15:48众所周知,迪杰斯特拉有个特性就是最早确定的点到源点的最小路径就越小,因此每当确定一个点到源点的最小路径,就看看是不是驻扎军队的点,如果是就直接输出,输出的点的一定是所有距离源点的驻扎军队的点的最小距离... -
知识表示学习1多元关系数据翻译嵌入2知识表示学习关系路径建模(公号回复“知识表示学习”下载彩标PDF典藏版...
2018-10-29 22:18:58知识表示学习1多元关系数据翻译嵌入2知识表示学习关系路径建模(公号回复“知识表示学习”下载彩标PDF典藏版资料) 原创: 秦陇纪 数据简化DataSimp 今天 数据简化DataSimp导读:医学AI读书会两篇论文:[1]Bordes A,... -
积分路径上有奇点的积分_多元微积分和一元微积分是否有本质区别,如果有,区别在哪?...
2020-12-09 22:22:57多元微积分是很多人的薄弱环节,它很有难度,但是十分重要,是微积分的灵魂。学好多元微积分必须放下对计算量的恐惧,而仅仅做到这一点还不够,还应该具备更高的眼光。假如多元微积分和一元微积分没有本质区别,我们... -
johnson最短路径
2017-06-30 17:14:04Johnson算法是求稀疏图的多元最短路径的算法,权值可以为负,但是不可以有负环。Johson算法是Bellman-Ford算法, Reweighting(重赋权重)和Dijkstra算法的大综合。主要的思想是使用dijstra算法对每个结点求单源最短路... -
最短路径算法汇总!
2020-10-18 22:13:28多元最短路径—求任意两顶点间的最短路径(Floyd算法) Bellman-ford(单源、解决负权边) SPFA(单源、解决负权边) 单源最短路径—无权图(BFS、DFS) 单源最短路径—有权图(Dijkstra算法) 一、单源最短路径... -
学术期刊发展路径选择
2020-06-26 03:23:13针对学术期刊发展面临的存在的危机及层层阻碍,在分析了我国学术期刊发展现状的基础上,阐述了学术期刊的发展链,引出学术期刊的路径选择应从数字化、多元化和市场化入手,并提出相应的路径模式和优势。研究认为,学术... -
matlab多元回归
2020-09-16 09:59:29如果想直接使用的话,要注意代码里面的路径,每个人运行的路径不一样。数据我就不上传了,大家想用,用自己的数据跑一下吧,注意矩阵的行和列,很多新手跑的时候认为跑不出来以为代码有问题,其实往往不是的。有什么... -
最短路径——Floyd
2017-06-12 16:10:02Floyd算法是基于动态规划的,依次扫描每个点,并以此点为中介,计算出经过该点的路径(i, j)的最短路径。 弗洛伊德(Floyd)算法过程: 1、用D[v][w]记录每一对顶点的最短距离。 2、依次扫描每一个点,并以其为 -
曲线积分与路径无关
2020-06-15 15:07:27在多元函数的积分中,从起点到终点可以有无数条积分路径。有的时候,无论选择哪一条路径,积分结果不变,只和起点和终点有关,那么这就是积分与路径无关 以P(x,y),Q(x,y)为例,在单连通区域D内,出现以下几种... -
最短路路径(1.1版待更新)
2019-03-24 00:02:00弗洛伊德算法是解决多元最短路径的算法(什么是多源, 顾名思义就是起点有多个, 跑完floyd算法就算出以每个顶点做起点到各个点的最短路径)。 2、时间复杂度 O(n^3), 空间复杂度O(n^2) 3、适用性: 1、多源最短路... -
创新煤炭企业物流管理体系的路径选择
2020-07-06 01:54:20就物流管理体系的内涵界定可知,其必然存在着人力、物力、信息平台等多元要件。这两个主要要件在生产任务导向下,惟有形成无缝衔接才能满足企业产能柔性化调整的要求。在创新煤炭企业物流管理体系之间,还应在与企业内...