精华内容
下载资源
问答
  • Floyd算法求解多元最短路径问题 ** 问题描述: 对于多个目标地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算法 首先分析这张图 就拿从1到3,可以直接1-&gt;3,也可以1-&gt;2-&gt;3,我们发现,通过一个“中转”的2,1-&gt;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。这样说可能有点乱,希望的对理解这个算法有点帮助。

    展开全文
  • 针对目前煤矿井下火灾救援模型过于复杂、对巷道安全因子的研究不够深入、未考虑灾后巷道交通网络连通度的问题,建立了基于多元信息评估的矿井火灾救援路径优化模型。对火灾后巷道内温度、瓦斯浓度、烟雾能见度等环境...
  • 最短路径1. 准备工作数据准备(以湖北省为例)环境2. 步骤2.1 截取湖北省数据2.1.1 新建地图(多源最短路径-湖北)2.1.2 内容列表窗口>>图层>>右键>>添加数据, 再全国行政区划分中导入省和市的...

    0. 最短路径

    • 数据结构中,图的相关知识中的一个重要知识点就是计算最短路径的问题。期中包括两个解决办法:
      1. 单源最短路径: Dijkstra算法.
      2. 多源最短路径:Floyd算法.
    • 问题:使用上述算法计算出来的最短路径长度,一般属于直线距离,如果用于计算城市间的最短距离,则不符合实际情况。
    • 城市间的各种联系往往基于路网发生,因此我们需要使用路网的距离作为两个城市间的实际距离。
      ArcGIS中提供了计算路网距离的方法,现以湖北省为例,使用ArcGIS计算各地级市之间的最短距离。

    1. 准备工作

    数据准备(以湖北省为例)

    • 准备湖北省边界、湖北各个市的边界和地级市驻点数据
    • 准备路网数据(国道、省道)
      链接:https://pan.baidu.com/s/1GVGuVsl-iEhqN25XiD9eVw 提取码:gi7h

    环境

    • ArcGIS 10.2
    • 激活网络分析模块
      • 菜单 >> 自定义 >> 扩展模块 >> 勾选Network Analyst
        Customer >> Extensions >> 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成本矩阵

    1. 打开ArcToolbox在这里插入图片描述
      选择里面的转换工具>> Excel >> 表转Excel
      在这里插入图片描述
      在输入表的下拉列表中选择OD成本矩阵中的线 >> 选择输出文件的路径和名字>> 点击确定在这里插入图片描述
      期中 Tota_长度, 为两个城市间最短路径的长度(单位: 米).
      在这里插入图片描述

    2.4 可视化

    2.4.1 生成城市点对

    想要画出路径图, 需要知道路径的起点和终点

    1. 导出路径的起点, 使用要素折点转点工具, ArcToolbox >> 数据管理工具 >> 要素 >> 要素折点转点工具.
      选取输入要素下拉列表中OD成本矩阵下的"线" >> 点类型选择START >> 确定
      在这里插入图片描述
    2. 导出路径的终点
      选取输入要素下拉列表中OD成本矩阵下的"线" >> 点类型选择END >> 确定
      在这里插入图片描述
      内容中增加了如下内容
      在这里插入图片描述

    2.4.2 新建路径

    1. 选择网络分析中的新建路径
      在这里插入图片描述
      网络分析窗口中增加了路径窗口
      在这里插入图片描述
    2. 增加停靠点
      右键点击停靠点 >> 加载位置
      在这里插入图片描述
      增加起点: 加载自下拉列表中选择,刚才添加的START的要素 >> name字段设为空 >> RouteName字段设为 name
      在这里插入图片描述
      增加终点: 加载自下拉列表中选择,刚才添加的END的要素 >> name字段设为空 >> RouteName字段设为 name
      增加了324条路径的648个停靠点
      在这里插入图片描述

    2.4.3 生成路径

    点击Network工具栏上的求解.生成路径
    在这里插入图片描述
    生成并显示了324条最短路径
    在这里插入图片描述

    3 收尾

    加上省界和市界的图层, 生成最终效果图
    在这里插入图片描述

    编辑后的数据下载

    展开全文
  • 基于理论回顾与案例分析,探讨煤炭企业股权多元化改革的有效实施路径,主要包括引入非国有资本参与国有企业改革、向发展潜力大和成长性好的非国有企业进行股权投资、实施员工持股计划、登陆资本市场并引进机构投资者。
  • 说明:最近在做捕鱼达人的游戏但是里面的路径点要求可以配置的所以就想到了自己绘制点的信息然后导出来配置表,结合网上的经验更改了些许,效果如下。步骤: 1.鼠标触摸在画布上面任意位置生成点点坐标 2.点击绘制...

    说明:最近在做捕鱼达人的游戏但是里面的路径点要求可以配置的所以就想到了自己绘制点的信息然后导出来配置表,结合网上的经验更改了些许,效果如下。

    步骤: 

     1.鼠标触摸在画布上面任意位置生成点坐标

     2.点击绘制可以生成目标曲线

     3.支持导出配置点到json 或者 text 文件并完成下载

     4.清空画布重新绘制

     5.后续完成撤销操作


    工具地址:下载


    展开全文
  • 单源最短路径 使用Bellman-Ford算法 SFPA算法(Bellman-Ford算法的改进) 使用dijstra算法 多源最短路径和拓扑排序 最小生成树 题目13.2链接 Minimum Spanning Tree 采用Prim算法 二者均采用邻接矩阵 第一...
  • 在《漫画:图的 “最短路径” 问题》一文中小灰介绍了单源最短路径算法 Dijkstra。当时漫画中我们遗留了一个问题:如何求得最短路径的详细节点,而不仅仅是距离?——在本篇中,我们将会给与解答。我们仍然以下面这...
  • 国别发展是一个复杂的问题,从严格的经济观点到更综合的愿景都可以指代。 这项研究从获得基本服务,水资源管理和捐助者的外部支持等方面分析了可持续发展。 根据22个变量对103个国家进行了分析,这些变量包括获得...
  • 众所周知,迪杰斯特拉有个特性就是最早确定的点到源点的最小路径就越小,因此每当确定一个点到源点的最小路径,就看看是不是驻扎军队的点,如果是就直接输出,输出的点的一定是所有距离源点的驻扎军队的点的最小距离...
  • 知识表示学习1多元关系数据翻译嵌入2知识表示学习关系路径建模(公号回复“知识表示学习”下载彩标PDF典藏版资料) 原创: 秦陇纪 数据简化DataSimp 今天 数据简化DataSimp导读:医学AI读书会两篇论文:[1]Bordes A,...
  • 多元微积分是很多人的薄弱环节,它很有难度,但是十分重要,是微积分的灵魂。学好多元微积分必须放下对计算量的恐惧,而仅仅做到这一点还不够,还应该具备更高的眼光。假如多元微积分和一元微积分没有本质区别,我们...
  • johnson最短路径

    2017-06-30 17:14:04
    Johnson算法是求稀疏图的多元最短路径的算法,权值可以为负,但是不可以有负环。Johson算法是Bellman-Ford算法, Reweighting(重赋权重)和Dijkstra算法的大综合。主要的思想是使用dijstra算法对每个结点求单源最短路...
  • 最短路径算法汇总!

    2020-10-18 22:13:28
    多元最短路径—求任意两顶点间的最短路径(Floyd算法) Bellman-ford(单源、解决负权边) SPFA(单源、解决负权边) 单源最短路径—无权图(BFS、DFS) 单源最短路径—有权图(Dijkstra算法) 一、单源最短路径...
  • 针对学术期刊发展面临的存在的危机及层层阻碍,在分析了我国学术期刊发展现状的基础上,阐述了学术期刊的发展链,引出学术期刊的路径选择应从数字化、多元化和市场化入手,并提出相应的路径模式和优势。研究认为,学术...
  • matlab多元回归

    2020-09-16 09:59:29
    如果想直接使用的话,要注意代码里面的路径,每个人运行的路径不一样。数据我就不上传了,大家想用,用自己的数据跑一下吧,注意矩阵的行和列,很多新手跑的时候认为跑不出来以为代码有问题,其实往往不是的。有什么...
  • 最短路径——Floyd

    2017-06-12 16:10:02
    Floyd算法是基于动态规划的,依次扫描每个点,并以此点为中介,计算出经过该点的路径(i, j)的最短路径。 弗洛伊德(Floyd)算法过程: 1、用D[v][w]记录每一对顶点的最短距离。 2、依次扫描每一个点,并以其为
  • 曲线积分与路径无关

    千次阅读 2020-06-15 15:07:27
    多元函数的积分中,从起点到终点可以有无数条积分路径。有的时候,无论选择哪一条路径,积分结果不变,只和起点和终点有关,那么这就是积分与路径无关 以P(x,y),Q(x,y)为例,在单连通区域D内,出现以下几种...
  • 弗洛伊德算法是解决多元最短路径的算法(什么是多源, 顾名思义就是起点有多个, 跑完floyd算法就算出以每个顶点做起点到各个点的最短路径)。 2、时间复杂度 O(n^3), 空间复杂度O(n^2) 3、适用性: 1、多源最短路...
  • 就物流管理体系的内涵界定可知,其必然存在着人力、物力、信息平台等多元要件。这两个主要要件在生产任务导向下,惟有形成无缝衔接才能满足企业产能柔性化调整的要求。在创新煤炭企业物流管理体系之间,还应在与企业内...

空空如也

空空如也

1 2 3 4 5 ... 12
收藏数 222
精华内容 88
关键字:

多元路径