空间分析的最短路径的两个算法

㈠ 图遍历算法之最短路径Dijkstra算法

最短路径问题是图论研究中一个经典算法问题，旨在寻找图中两节点或单个节点到其他节点之间的最短路径。根据问题的不同，算法的具体形式包括：

常用的最短路径算法包括：Dijkstra算法，A 算法，Bellman-Ford算法，SPFA算法（Bellman-Ford算法的改进版本），Floyd-Warshall算法，Johnson算法以及Bi-direction BFS算法。本文将重点介绍Dijkstra算法的原理以及实现。

Dijkstra算法，翻译作戴克斯特拉算法或迪杰斯特拉算法，于1956年由荷兰计算机科学家艾兹赫尔.戴克斯特拉提出，用于解决赋权有向图的 单源最短路径问题 。所谓单源最短路径问题是指确定起点，寻找该节点到图中任意节点的最短路径，算法可用于寻找两个城市中的最短路径或是解决着名的旅行商问题。

问题描述 ：在无向图 中， 为图节点的集合， 为节点之间连线边的集合。假设每条边 的权重为 ，找到由顶点 到其余各个节点的最短路径（单源最短路径）。

为带权无向图，图中顶点 分为两组，第一组为已求出最短路径的顶点集合（用 表示）。初始时 只有源点，当求得一条最短路径时，便将新增顶点添加进 ，直到所有顶点加入 中，算法结束。第二组为未确定最短路径顶点集合（用 表示），随着 中顶点增加， 中顶点逐渐减少。

以下图为例，对Dijkstra算法的工作流程进行演示（以顶点 为起点）：

注：
01） 是已计算出最短路径的顶点集合；
02） 是未计算出最短路径的顶点集合；
03） 表示顶点 到顶点 的最短距离为3
第1步 ：选取顶点 添加进

第2步 ：选取顶点 添加进 ，更新 中顶点最短距离

第3步 ：选取顶点 添加进 ，更新 中顶点最短距离

第4步 ：选取顶点 添加进 ，更新 中顶点最短距离

第5步 ：选取顶点 添加进 ，更新 中顶点最短距离

第6步 ：选取顶点 添加进 ，更新 中顶点最短距离

第7步 ：选取顶点 添加进 ，更新 中顶点最短距离

示例：node编号1-7分别代表A,B,C,D,E,F,G

(s.paths <- shortest.paths(g, algorithm = "dijkstra"))输出结果：

(s.paths <- shortest.paths(g,4, algorithm = "dijkstra"))输出结果：

示例：

找到D（4）到G（7）的最短路径：

[1] 维基网络，最短路径问题： https://zh.wikipedia.org/wiki/%E6%9C%80%E7%9F%AD%E8%B7%AF%E9%97%AE%E9%A2%98 ；
[2]CSDN，Dijkstra算法原理： https://blog.csdn.net/yalishadaa/article/details/55827681 ;
[3]RDocumentation: https://www.rdocumentation.org/packages/RNeo4j/versions/1.6.4/topics/dijkstra ;
[4]RDocumentation: https://www.rdocumentation.org/packages/igraph/versions/0.1.1/topics/shortest.paths ;
[5]Pypi: https://pypi.org/project/Dijkstar/

㈡ 求解：图论中常见的最短路径算法有几种都是什么

主要是有三种、、

第一种是最直接的贪心dijkstra算法、、可以利用堆数据结构进行优化、、缺点就是不能求有负权的最短路与判断负环、、

第二种是bellman-ford算法、、根据松弛操作的性质是可以来判断负环的、、时间复杂度是O(nm)的、、

第三种是SPFA算法、、把他单独拿出来作为一种算法并不是非常好的、、他的实质应该是上面的bellman-ford算法的队列优化时间复杂度更低、O(KE)、K的值约等于2、、

㈢ 关于时间依赖的最短路径算法

Dijkstra 最短路径算法的一种高效率实现*

随着计算机的普及以及地理信息科学的发展，GIS因其强大的功能得到日益广泛和深入的应用。网络分析作为GIS最主要的功能之一，在电子导航、交通旅游、城市规划以及电力、通讯等各种管网、管线的布局设计中发挥了重要的作用，而网络分析中最基本最关键的问题是最短路径问题。最短路径不仅仅指一般地理意义上的距离最短，还可以引申到其他的度量，如时间、费用、线路容量等。相应地，最短路径问题就成为最快路径问题、最低费用问题等。由于最短路径问题在实际中常用于汽车导航系统以及各种应急系统等（如110报警、119火警以及医疗救护系统），这些系统一般要求计算出到出事地点的最佳路线的时间应该在1 s～3 s内，在行车过程中还需要实时计算出车辆前方的行驶路线，这就决定了最短路径问题的实现应该是高效率的。其实,无论是距离最短、时间最快还是费用最低，它们的核心算法都是最短路径算法。经典的最短路径算法——Dijkstra算法是目前多数系统解决最短路径问题采用的理论基础，只是不同系统对Dijkstra算法采用了不同的实现方法。
据统计，目前提出的此类最短路径的算法大约有17种。F.Benjamin Zhan等人对其中的15种进行了测试，结果显示有3种效果比较好，它们分别是：TQQ（graph growth with two queues）、DKA (the Dijkstra's algorithm implemented with approximate buckets) 以及 DKD (the Dijkstra�s algorithm implemented with double buckets )，这些算法的具体内容可以参见文献〔1〕。其中TQQ算法的基础是图增长理论，较适合于计算单源点到其他所有点间的最短距离；后两种算法则是基于Dijkstra的算法，更适合于计算两点间的最短路径问题〔1〕。总体来说，这些算法采用的数据结构及其实现方法由于受到当时计算机硬件发展水平的限制，将空间存储问题放到了一个很重要的位置，以牺牲适当的时间效率来换取空间节省。目前，空间存储问题已不是要考虑的主要问题，因此有必要对已有的算法重新进行考虑并进行改进，可以用空间换时间来提高最短路径算法的效率。
1 经典Dijkstra算法的主要思想
Dijkstra算法的基本思路是：假设每个点都有一对标号 (dj, pj)，其中dj是从起源点s到点j的最短路径的长度 (从顶点到其本身的最短路径是零路(没有弧的路)，其长度等于零)；pj则是从s到j的最短路径中j点的前一点。求解从起源点s到点j的最短路径算法的基本过程如下：
1) 初始化。起源点设置为：① ds=0, ps为空;② 所有其他点: di=∞, pi= ;③ 标记起源点s，记k=s,其他所有点设为未标记的。
2) 检验从所有已标记的点k到其直接连接的未标记的点j的距离，并设置：
dj=min〔dj, dk+lkj〕
式中，lkj是从点k到j的直接连接距离。
3) 选取下一个点。从所有未标记的结点中，选取dj 中最小的一个i：
di=min〔dj, 所有未标记的点j〕
点i就被选为最短路径中的一点，并设为已标记的。
4) 找到点i的前一点。从已标记的点中找到直接连接到点i的点j*，作为前一点,设置：
i=j*
5) 标记点i。如果所有点已标记，则算法完全推出，否则，记k=i，转到2) 再继续。
2 已有的Dijkstra算法的实现
从上面可以看出，在按标记法实现Dijkstra算法的过程中，核心步骤就是从未标记的点中选择一个权值最小的弧段，即上面所述算法的2)～5)步。这是一个循环比较的过程，如果不采用任何技巧，未标记点将以无序的形式存放在一个链表或数组中。那么要选择一个权值最小的弧段就必须把所有的点都扫描一遍，在大数据量的情况下，这无疑是一个制约计算速度的瓶颈。要解决这个问题，最有效的做法就是将这些要扫描的点按其所在边的权值进行顺序排列，这样每循环一次即可取到符合条件的点，可大大提高算法的执行效率。另外，GIS中的数据 (如道路、管网、线路等)要进行最短路径的计算，就必须首先将其按结点和边的关系抽象为图的结构，这在GIS中称为构建网络的拓扑关系 (由于这里的计算与面无关，所以拓扑关系中只记录了线与结点的关系而无线与面的关系，是不完备的拓扑关系)。如果用一个矩阵来表示这个网络，不但所需空间巨大，而且效率会很低。下面主要就如何用一个简洁高效的结构表示网的拓扑关系以及快速搜索技术的实现进行讨论。
网络在数学和计算机领域中被抽象为图，所以其基础是图的存储表示。一般而言，无向图可以用邻接矩阵和邻接多重表来表示，而有向图则可以用邻接表和十字链表〔4〕 表示，其优缺点的比较见表 1。
表 1 几种图的存储结构的比较
Tab. 1 The Comparsion of Several Graph for Storing Structures
名 称 实现方法 优 点 缺 点 时间复杂度
邻接矩阵 二维数组 1. 易判断两点间的关系 占用空间大 O(n2+m*n)
2. 容易求得顶点的度
邻接表 链表 1. 节省空间 1. 不易判断两点间的关系 O(n+m)或O(n*m)
2. 易得到顶点的出度 2. 不易得到顶点的入度
十字链表 链表 1. 空间要求较小 结构较复杂 同邻接表
2.易求得顶点的出度和入度
邻接多重表 链表 1. 节省空间 结构较复杂 同邻接表
2. 易判断两点间的关系

目前,对于算法中快速搜索技术的实现，主要有桶结构法、队列法以及堆栈实现法。TQQ、DKA 以及 DKD 在这方面是比较典型的代表。TQQ虽然是基于图增长理论的，但是快速搜索技术同样是其算法实现的关键，它用两个FIFO的队列实现了一个双端队列结构来支持搜索过程〔1〕。
DKA和DKD是采用如图 1 所示的桶结构来支持这个运算，其算法的命名也来源于此。在DKA算法中，第i个桶内装有权值落在 〔b*i, (i+1)*b) 范围内的可供扫描的点，其中b是视网络中边的权值分布情况而定的一个常数。每一个桶用队列来维护，这样每个点有可能被多次扫描，但最多次数不会超过b次。最坏情况下，DKA的时间复杂度将会是O(m*b+n(b+C/b))，其中，C为图中边的最大权值。DKD将点按权值的范围大小分装在两个级别的桶内，高级别的桶保存权值较大的点，相应的权值较小的点都放在低级别的桶内，每次扫描都只针对低级别桶中的点。当然随着点的插入和删除，两个桶内的点是需要动态调整的。在DKA算法中，给每个桶一定的范围以及DKD中使用双桶，在一定程度上都是以空间换时间的做法，需要改进。

图 1 一个桶结构的示例
Fig. 1 An Example of the Bucket Data Structure
3 本文提出的Dijkstra算法实现
3.1 网络拓扑关系的建立
上面介绍的各种图的存储结构考虑了图在理论上的各种特征，如有向、无向、带权、出度、入度等。而GIS中的网络一般为各种道路、管网、管线等，这些网络在具有图理论中的基本特征的同时，更具有自己在实际中的一些特点。首先，在GIS中大多数网络都是有向带权图，如道路有单双向问题，电流、水流都有方向（如果是无向图也可归为有向图的特例），且不同的方向可能有不同的权值。更重要的一点是，根据最短路径算法的特性可以知道，顶点的出度是个重要指标，但是其入度在算法里则不必考虑。综合以上4种存储结构的优缺点， 笔者采用了两个数组来存储网络图，一个用来存储和弧段相关的数据（Net-Arc List），另一个则存储和顶点相关的数据（Net-Node Index）。Net-Arc List用一个数组维护并且以以弧段起点的点号来顺序排列，同一起点的弧段可以任意排序。这个数组类似于邻接矩阵的压缩存储方式，其内容则具有邻接多重表的特点，即一条边以两顶点表示。Net-Node Index则相当于一个记录了顶点出度的索引表，通过它可以很容易地得到此顶点的出度以及与它相连的第一条弧段在弧段数组中的位置。此外，属性数据作为GIS不可少的一部分也是必须记录的。这样，计算最佳路径所需的网络信息已经完备了。在顶点已编号的情况下，建立Net-Arc List和Net-Node Index两个表以及对Net-Arc List的排序，其时间复杂度共为O(2n+lgn)，否则为O(m+2n+lgn)。这个结构所需的空间也是必要条件下最小的，记录了m个顶点以及n条边的相关信息，与邻接多重表是相同的。图 2 是采用这个结构的示意图。
3.2 快速搜索技术的实现
无论何种算法，一个基本思想都是将点按权值的大小顺序排列，以节省操作时间。前面已经提到过，这两个算法都是以时间换空间的算法，所以在这里有必要讨论存储空间问题 (这部分空间的大小依赖于点的个数及其出度)。根据图中顶点和边的个数可以求出顶点的平均出度e=m/n（m为边数，n为顶点数），这个数值代表了图的连通程度，一般在GIS的网络图中，e∈〔2,5〕。这样,如果当前永久标记的点为t个，那么，下一步需扫描点的个数就约为t～4t个。如果采用链表结构，按实际应用中的网络规模大小，所需的总存储空间一般不会超过100 K。所以完全没有必要采用以时间换空间的做法，相反以空间换时间的做法是完全可行的。在实现这部分时，笔者采用了一个FIFO队列，相应的操作主要是插入、排序和删除，插入和删除的时间复杂度都是O(1)，所以关键问题在于选择一个合适的排序算法。一般可供选择的排序算法有快速排序、堆排序以及归并排序等，其实现的平均时间都为O(nlgn)。经过比较实验，笔者选择了快速排序法。另外，Visual C++提供的run-time库也提供了现成的快速排序的函数qsort( )可供使用。

图 2 基于最佳路径计算的网络拓扑表示
Fig. 2 The Presentation of the Network Topology
Used for Computing the Shortest Path
按照以上思路，笔者用Visual C++实现了吉奥之星（GeoStar）中的最佳路径模块。以北京的街道为数据（共6 313个结点，9 214条弧段(双向)），在主频为133、硬盘为1 G、内存为32 M的机器上，计算一条贯穿全城、长为155.06 km的线路，约需1 s～2 s。如图 3所示。

图 3 GeoStar中最佳路径实现示意图

ps:图片没有办法贴上去.
你可以参考《算法导论》第二版

㈣ 求图中任意两点之间最短路径有什么算法

单源节点到其他任意节点的最短路径采用Dijkstra算法，任意两个节点之间的最短路径使用Floyd算法，这两个算法有很多地方可以找打。

㈤ 最短路径的两点怎么找

最短路径的两点可以通过一个定义两点之间直线最短来决定最短的路径。

地理信息系统简称GIS，是一种以采集、存储、管理、分析和描述地球表面与地理分布有关数据的空间信息系统。它能显示数据的空间分布，并具有强大的空间查询、分析、模拟、统计和预测等功能。故寻求两点之间最短、最快或景点最多的路径可应用GIS的查询和分析功能。

最短路径介绍

最短路径问题是图论研究中的一个经典算法问题， 旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。 算法具体的形式包括：确定起点的最短路径问题 - 即已知起始结点，求最短路径的问题。

确定终点的最短路径问题 - 与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。

㈥ 数据结构中关键路径和最短路径有什么简便的方法可以求得吗

额，什么是简便的方法呢。
我只知道可以利用事件的最早最晚发生时间来递推求关键路径。
而最短路径两种算法：迪杰特斯拉和弗洛伊德。
这个直接网络都有，我觉得它们已经很简便了，当然我相信会有其他的算法，但太简便的应该还没有，因为如果有那么好的的算法，为什么教科书上不采用呢。

㈦ 最短路径算法

Dijkstra算法，A*算法和D*算法

Dijkstra算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。

Dijkstra算法是很有代表性的最短路算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。

Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表方式，Drew为了和下面要介绍的 A* 算法和 D* 算法表述一致，这里均采用OPEN,CLOSE表的方式。

大概过程：
创建两个表，OPEN, CLOSE。
OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。
1． 访问路网中里起始点最近且没有被检查过的点，把这个点放入OPEN组中等待检查。
2． 从OPEN表中找出距起始点最近的点，找出这个点的所有子节点，把这个点放到CLOSE表中。
3． 遍历考察这个点的子节点。求出这些子节点距起始点的距离值，放子节点到OPEN表中。
4． 重复2，3，步。直到OPEN表为空，或找到目标点。

提高Dijkstra搜索速度的方法很多，常用的有数据结构采用Binary heap的方法，和用Dijkstra从起始点和终点同时搜索的方法。

A*（A-Star)算法是一种启发式算法，是静态路网中求解最短路最有效的方法。

公式表示为： f(n)=g(n)+h(n),
其中f(n) 是节点n从初始点到目标点的估价函数，
g(n) 是在状态空间中从初始节点到n节点的实际代价，
h(n)是从n到目标节点最佳路径的估计代价。

保证找到最短路径（最优解的）条件，关键在于估价函数h(n)的选取：
估价值h(n)<= n到目标节点的距离实际值，这种情况下，搜索的点数多，搜索范围大，效率低。但能得到最优解。
如果 估价值>实际值, 搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。
估价值与实际值越接近，估价函数取得就越好。
例如对于几何路网来说，可以取两节点间欧几理德距离（直线距离）做为估价值，即f=g(n)+sqrt((dx-nx)*(dx-nx)+(dy-ny)*(dy-ny))；这样估价函数f在g值一定的情况下，会或多或少的受估价值h的制约，节点距目标点近，h值小，f值相对就小，能保证最短路的搜索向终点的方向进行。明显优于Dijstra算法的毫无无方向的向四周搜索。
conditions of heuristic
Optimistic (must be less than or equal to the real cost)
As close to the real cost as possible
主要搜索过程：
创建两个表，OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。
遍历当前节点的各个节点，将n节点放入CLOSE中，取n节点的子节点X,->算X的估价值->
While(OPEN!=NULL)
{
从OPEN表中取估价值f最小的节点n;
if(n节点==目标节点) break;
else
{
if(X in OPEN) 比较两个X的估价值f //注意是同一个节点的两个不同路径的估价值
if( X的估价值小于OPEN表的估价值 )
更新OPEN表中的估价值; //取最小路径的估价值
if(X in CLOSE) 比较两个X的估价值 //注意是同一个节点的两个不同路径的估价值
if( X的估价值小于CLOSE表的估价值 )
更新CLOSE表中的估价值; 把X节点放入OPEN //取最小路径的估价值
if(X not in both)
求X的估价值;
并将X插入OPEN表中; //还没有排序
}
将n节点插入CLOSE表中;
按照估价值将OPEN表中的节点排序; //实际上是比较OPEN表内节点f的大小，从最小路径的节点向下进行。
}

A*算法和Dijistra算法的区别在于有无估价值，Dijistra算法相当于A*算法中估价值为0的情况。

动态路网，最短路算法 D*A* 在静态路网中非常有效（very efficient for static worlds），但不适于在动态路网，环境如权重等不断变化的动态环境下。

D*是动态A*（D-Star,Dynamic A*） 卡内及梅隆机器人中心的Stentz在1994和1995年两篇文章提出，主要用于机器人探路。是火星探测器采用的寻路算法。

主要方法：
1.先用Dijstra算法从目标节点G向起始节点搜索。储存路网中目标点到各个节点的最短路和该位置到目标点的实际值h,k（k为所有变化h之中最小的值,当前为k=h。每个节点包含上一节点到目标点的最短路信息1(2),2(5),5(4)，4（7）。则1到4的最短路为1-2-5-4。
原OPEN和CLOSE中节点信息保存。
2.机器人沿最短路开始移动，在移动的下一节点没有变化时，无需计算，利用上一步Dijstra计算出的最短路信息从出发点向后追述即可，当在Y点探测到下一节点X状态发生改变，如堵塞。机器人首先调整自己在当前位置Y到目标点G的实际值h(Y)，h(Y)=X到Y的新权值c(X,Y)+X的原实际值h(X).X为下一节点(到目标点方向Y->X->G），Y是当前点。k值取h值变化前后的最小。
3.用A*或其它算法计算，这里假设用A*算法,遍历Y的子节点，点放入CLOSE,调整Y的子节点a的h值，h(a)=h(Y)+Y到子节点a的权重C(Y,a),比较a点是否存在于OPEN和CLOSE中，方法如下：
while()
{
从OPEN表中取k值最小的节点Y;
遍历Y的子节点a,计算a的h值 h(a)=h(Y)+Y到子节点a的权重C(Y,a)
{
if(a in OPEN) 比较两个a的h值
if( a的h值小于OPEN表a的h值 )
{ 更新OPEN表中a的h值;k值取最小的h值
有未受影响的最短路经存在
break;
}
if(a in CLOSE) 比较两个a的h值 //注意是同一个节点的两个不同路径的估价值
if( a的h值小于CLOSE表的h值 )
{
更新CLOSE表中a的h值; k值取最小的h值;将a节点放入OPEN表
有未受影响的最短路经存在
break;
}
if(a not in both)
将a插入OPEN表中; //还没有排序
}
放Y到CLOSE表；
OPEN表比较k值大小进行排序；
}
机器人利用第一步Dijstra计算出的最短路信息从a点到目标点的最短路经进行。

D*算法在动态环境中寻路非常有效，向目标点移动中，只检查最短路径上下一节点或临近节点的变化情况，如机器人寻路等情况。对于距离远的最短路径上发生的变化，则感觉不太适用。

㈧ 每一对顶点之间的最短路径是什么

每一对顶点之间的最短路径是指对于给定的带权有向图G＝（v，E），要对G中任意一对顶点有序对（vi，vj）（vi≠vj），找出vi到vj的最短距离和vj到vi的最短距离。

解决此问题的一个有效方法是：轮流以每一个顶点为源点，重复执行Dijkstra算法n次，即可求得有向图G＝（v，E）中每一对顶点间的最短路径，总的时间复杂度为0（n2）。

弗洛伊德（Floyd）提出了另一个求任意两顶点之间最短路径的算法，虽然其时间复杂度也是0（n2），但算法形式更为简明，易于理解与编程。

1.弗洛伊德算法的思想弗洛伊德算法是从图的邻接矩阵开始，按照顶点v0，v1，v2，v2，…，vn的次序，分别以每个顶点vk（0≤k＜n）作为新考虑的中间点，在第k－1次运算D（k－1）的基础上，求出每一对顶点之间vi到vj的最短路径长度D（k）［i］［j］，计算公式为：

D（k）［i］［j］＝min｛D（k－1）［i］［j］，D（k－1）［i］［k］＋D（k－1）［k］［j］｝重复执行n次后，D（k）［i］［j］中保留的值就是每对顶点的vi到vj的最短路径长度。

2.弗洛伊德算法的步骤（1）从图的带权邻接矩阵G．arcs［］［］开始，即D（－1）＝arcs［］［］，每次以上一次D（k－1）为基础，用公式D（k）［i］［j］＝min｛D（k－1）［i］［j］，D（k－1）［i］［k］＋D（k－1）［k］［j］｝计算出D（k）［i］［j］的值，即D（k－1）［i］［k］＋D（k－1）［k］［j］＜D（k－1）［i］［j］才修改，若D（k）［i］［j］修改过，则相应的路径P（k）［i］［j］也要作相应的修改，即P（k）［i］［j］＝P（k－1）［i］［k］＋P（k－1）［k］［j］。

（2）重复上述过程n次后，D（k）［i］［j］中保存的就是每一对顶点的最短路径长度，P（k）［i］［j］中保存的就是每一对顶点的最短路径。

说明：从计算公式可以看出，i＝j是对角线上的元素；i＝k是i行上的元素；j＝k是j列上的元素，这些特殊的顶点不用计算，保留原来的数据值。因此，计算的数据元素减少了很多。