**
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->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。这样说可能有点乱，希望的对理解这个算法有点帮助。

目录
0. 最短路径
1. 准备工作
数据准备（以湖北省为例）
环境
2. 步骤
2.1 截取湖北省数据
2.1.1 新建地图（多源最短路径-湖北）
2.1.2 内容列表窗口>>图层>>右键>>添加数据, 再全国行政区划分中导入省和市的矢量图
2.1.3 对图层中的省点击右键>>打开属性表
2.1.4 导出湖北省的边界
2.1.5 导出地级市边界
2.2 创建网络数据集
2.2.1 创建文件数据库
2.2.2 导入要素类
2.2.3 创建网络数据集
2.3 计算城市间网络距离
2.3.1 打开网络分析窗口
2.3.2 创建OD成本矩阵
2.3.3 添加起始点和目的地点
2.3.4 生成OD 成本矩阵
2.3.5 导出OD成本矩阵
2.4 可视化
2.4.1 生成城市点对
2.4.2 新建路径
2.4.3 生成路径
3 收尾
编辑后的数据下载

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





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 收尾
加上省界和市界的图层, 生成最终效果图


编辑后的数据下载

说明:最近在做捕鱼达人的游戏但是里面的路径点要求可以配置的所以就想到了自己绘制点的信息然后导出来配置表，结合网上的经验更改了些许，效果如下。
步骤: 
 1.鼠标触摸在画布上面任意位置生成点坐标
 2.点击绘制可以生成目标曲线
 3.支持导出配置点到json 或者 text 文件并完成下载
 4.清空画布重新绘制
 5.后续完成撤销操作

工具地址:下载