最佳路径
-
2023年2月28日发(作者：无锡儿童医院)路径分析是GIS中最基本的功能，其核心是对最佳路径的求解。从网络模型的角
度看，最佳路径的求解是在指定网络的两个结点之间找一条阻碍强度最小的路
径。另一种路径分析功能是求解最佳游历方案，又分为弧段最佳游历方案求解和
结点最佳游历方案求解两种。
最佳路径分析也称最优路径分析，以最短路径分析为主。这里“最佳”包含很多
含义，不仅指一般地理意义上的距离最短，还可以是成本最少、耗费时间最短、
资源流量（容量）最大、线路利用率最高等标准。很多网络相关问题，如最可
靠路径问题、最大容量路径问题、易达性评价问题和各种路径分配问题均可纳
入最佳路径问题的范畴之中。无论判断标准和实际问题中的约束条件如何变化，
其核心实现方法都是最短路径算法。
最短路径问题从算法研究的角度考虑最短路径问题通常可归纳为两大类：一类
是所有点对之间的最短路径，另一类是单源点间的最短路径问题。
网络分析：最佳路径问题
“最佳路径”中的“佳”包含很多含义，它不仅可以指一般地理意义上的距离
最短，还可以是时间最短、费用最少、线路利用率最高等标准。但是无论引申
为何种判断标准，其核心实现方法都是最短路径算法。
最短路径的数据基础是网络，组成网络的每一条弧段都有一个相应的权值，用
来表示此弧段所连接的两结点间阻抗值。在数学模型中，这些权值可以为正值，
也可以为负值。由于在GIS中一般的最短路径问题都不涉及负回路的情况，因此
以下所有的讨论中假定弧段的权值都为非负值。
若一条弧段(vi，vj)的权值表示结点vi和vj间的长度，那么道路u＝{e1，e2，…，
ek}的长度即为u上所有边的长度之和。所谓最短路径问题就是在vi和vj之间的
所有路径中，寻求长度最小的路径，这样的路径称为从vi到vj的最短路径。
最短路径问题的算法一般分为两大类：一类是所有点对间的最短路径，另一类
则是单源点间的最短路径问题，其各自的求解方法是不同的。
5.3.2最佳路径分析
最佳路径分析也称最优路径分析，以最短路径分析为主，一直是计算机科学、运筹学、
交通工程学、地理信息科学等学科的研究热点。这里“最佳”包含很多含义，不仅指一般地
理意义上的距离最短，还可以是成本最少、耗费时间最短、资源流量（容量）最大、线路利
用率最高等标准。很多网络相关问题，如最可靠路径问题、最大容量路径问题、易达性评价
问题和各种路径分配问题均可纳入最佳路径问题的范畴之中。无论判断标准和实际问题中的
约束条件如何变化，其核心实现方法都是最短路径算法。
地理网络因地理元素属性的不同而表现为同形不同性的网络形式，为了进行网络路径分
析，需要将网络转换成加权有向图，即给网络中的弧段赋以权值，权值要根据约束条件而确
定。若一条弧段的权表示起始结点和终止结点之间的长度，那么任意两结点间的一条路径的
长度即为这条路上所有边的长度之和。最短路径问题就是在两结点之间的所有路径中，寻求
长度最小的路径，这样的路径称为两结点间的最短路径。
最短路径问题的表达是比较简单的，从算法研究的角度考虑最短路径问题通常可归纳为
两大类：一类是所有点对之间的最短路径，另一类是单源点间的最短路径问题。
1.最短路径算法
（1）Dijkstra算法基本思想
戴克斯徒拉（Dijkstra）算法是ra于1959年提出的一种按路径长度递增的次序
产生最短路径的算法，此算法被认为是解决单源点间最短路径问题比较经典而且有效的算
法。其基本思路是：假设每个点都有一对标号（d
j
,p
j
），其中d
j
是从起源点s到点j的最短路
径的长度（从顶点到其本身的最短路径是零路（没有弧的路），其长度等于零）；p
j
则是从s
到j的最短路径中j点的前一点。求解从起源点s到点j的最短路径算法也称标号法或染色
法，其基本过程如下：
①初始化。起源点设置为d
s
=0，p
s
为空，并标记起源点s，
记k=s，其他所有点设为未标记点。
②检验从所有已标记的点k到其直接连接的未标记的点j的
距离，并设置
d
j
=min［d
j
,d
k
+l
kj
］
其中，l
kj
为从点k到j的直接连接距离。
③选取下一个点。从所有未标记的结点中，选取d
j
中最小
的一个i
d
i
=min［d
j
,所有未标记的点j］
点i就被选为最短路径中的一点，并设为已标记的点。
④找到点i的前一点。从已标记的点中找到直接连接到点i的点j*，作为前一点，记为
i=j*
⑤标记点i。如果所有点已标记，则算法完全推出，否则，记k=i，重复步骤②③④。
图5.37为某一带权有向图，若对其施行Dijkstra算法，则所得从V
0
到其余各顶点的最
短路径以及运算过程中距离的变化情况如表5.5所示。
通过上述例子可知，在求解从起源点到某一特定终点的最短路径过程中还可得到起源点
到其他各点的最短路径，因此，这一计算过程的时间复杂度是O(n2)，其中n为网络中的结
点数。
（2）弗洛伊德算法
弗洛伊德（Floyd）算法能够求得每一对顶点之间的最短路径，其基本思想是：假设求
从顶点V
i
到V
j
的最短路径。若从V
i
到V
j
有弧，则从V
i
到V
j
存在一条长度为d
ij
的路径，该
路径不一定是最短路径，需要进行n次试探。首先判别弧（V
i
,V
1
）和弧（V
1
,V
j
）是否存在
（即考虑路径（V
i
,V
1
,V
j
）是否存在）。如果存在，则比较（V
i
,V
j
）和（V
i
,V
1
,V
j
）的路径长度，
较短者为从V
i
到V
j
的中间顶点的序号不大于1的最短路径。假如在路径上再增加一个顶点
终
点
从源点V
0
到各终点的距离值和最短路径的求解过程
i=1i=2i=3i=4i=5
V
1
∞∞∞∞∞
V
2
10
（V
0
,V
2
）
V
3
∞
60
（V
0
,V
2
,V
3
）
50
（V
0
,V
4
,V
3
）
V
4
30
（V
0
,V
4
）
30
（V
0
,V
4
）
V
5
100
（V
0
,V
5
）
100
（V
0
,V
5
）
90
（V
0
,V
4
,V
5
）
60
（V
0
,V
4
,V
3
,V
5
）
V
j
V
2
V
4
V
3
V
5
S
﹛V
0
,V
2
﹜﹛V
0
,V
2
,V
3
﹜﹛V
0
,V
2
,V
3
,V
4
﹜﹛V
0
,V
2
,V
3
,V
4
,V
5
﹜
表5.5Dijkstra算法示例及计算过程
V
2
V
0
V
1
100
V
3
V
5
V
4
60
20
30
10
10
50
5
图5.37带权的有向图
V
2
，若路径（V
i
,…,V
2
）和路径（V
2
,…,V
j
）分别是当前找到的中间顶点的序号不大于1的
最短路径，那么后来的路径（V
i
,…,V
2
,…,V
j
）就有可能是从V
i
到V
j
的中间顶点的序号不大
于2的最短路径。将它和已经得到的从V
i
到V
j
的中间顶点的序号不大于1的最短路径相比
较，从中选出中间顶点的序号不大于2的最短路径之后，再增加一个顶点V
3
，继续进行试
探。依次类推，在经过n次比较之后，最后求得的必是从V
i
到V
j
的最短路径。按此方法，
可同时求得各对顶点间的最短路径。算法共需3层循环，总的时间复杂度是O(n3)。
（3）矩阵算法
该算法是利用矩阵来求出图的最短距离矩阵。假设A=(a
i,j
)
n×n
是带权无向图的邻接矩阵，
则A[2]=(a
i,j
[2])
n×n
，其中a
i,j
=min﹛a
i1
+a
1j
,a
i2
+a
2j
,…,a
ik
+a
kj
﹜，这里a
i1
+a
1j
表示从结点i经过
中间点1到结点j的路径长度，a
i2
+a
2j
表示从结点i经过中间点2到结点j的路径长度，其余
各项的意义与此相同，都表示从结点i经过一个中间点到结点j的路径长度，a
i,j
取它们中的
最小值，其意义就是从结点i最多经过一个中间点到结点j的所有路径中长度最短的那条路
径。同理可知，A[k]=(a
i,j
[k])
n×n
中a
i,j
[k]表示从结点i最多经过（k-1）个中间点到结点j的所有
路径中长度最短的那条路径。图的阶数是n，从i到j的简单路径最多经过n-2个中间结点，
故只需要求到A［
n-2
］即可，然后比较A,A[2],A[3],…,A［
n-2
］，取其中最小的一项就是从结点i
到结点j的所有路径中长度最小的那条路径。算法步骤可表示为
①已知图的邻接矩阵A；
②求出A,A[2],A[3],…,A［
n-2
］；
③D=AA[2]A[3]…A［
n-2
］=(d
i,j
)
n×n
。
最终得到的D为图的最短距离矩阵。求出矩阵中的每个值需要进行n次计算，求出矩
阵中的所有元素值需要进行n2次计算，最后又需要进行n次比较，所以该算法的时间复杂
度是O(n4)。
以上三种算法各有优缺点，下面仅就适用范围、功能、时间复杂度、求解次短路径能力
等方面进行比较，以便在使用中选择更利于问题解决的方法。
Dijkstra算法、弗洛伊德算法都可适用于无向图或有向图，而矩阵算法本身仅适用于无
向图，但经改进后也可用于有向图；Dijkstra算法每次只能求出一个起源点到其余各点的路
径，弗洛伊德算法和矩阵算法都能够求得所有顶点间的最短路径；这三种算法的时间复杂度
依次为O(n2)、O(n3)、O(n4)；另外，矩阵算法还能求出次短路径，其他两种算法则不能。
2.最短路径算法的优化
最佳路径分析在汽车导航系统和各种应急系统（如110报警、119火警以及医疗救护系
统等）中应用非常广泛，系统应用需求决定了最佳路径分析应是高效率的，比如一般要求计
算出到出事地点的最佳路径的时间必须是在1～3s内，且在行车过程中需要实时计算出车辆
前方的行驶路线。但前面介绍的三种算法在时间复杂度上都不尽如人意，很难满足不断发展
的各种系统的要求，从而促使人们考虑从各个角度解决其实现的效率问题。针对不同的网络
特征、应用需求及具体的软硬件环境，各种最短路径算法不断涌现，在空间复杂度、时间复
杂度、易实现性及应用范围等方面各具特色。例如，以提出最大相关边数概念为特点的相关
边算法，用点—边相关矩阵描述网络结构，既节约了存储空间，又提高勒运算速度；类似地
还有邻接结点算法以及引入估价函数或者采用二叉堆结构来实现的改进Dijkstra算法，等等。
在此不一一列举，如有兴趣可查阅相关文献。
3.路径分析的实现
实现路径分析最关键的问题有两个：一是选用何种数据结构才能够满足庞大网络数据占
据较小存储空间的要求，一是采用哪一类搜索算法来求得最优化的解，而且在实现时间、应
用普遍性、空间搜索复杂程度上满足用户的要求，下面就以路径分析应用最广泛的交通道路
网络为例，提供一个解决实际问题的基本模式。
假定某地区交通管理部门接到举报在该区域内某一地点发生交通事故，需要有关人员立
刻赶到现场，选择一条路途最短的行进路线到达指定地点。在解决问题之前要了解交通网络
数据的基本特征，如数据量的大小、数据的存储格式、数据的来源以及时间等，交通道路网
不仅包含网络本身的几何拓扑特征，还包含了大量的与应用有关的数据（如单行道、禁行道
等）以及反映地理位置特征的经纬度数据，在应用最短路径算法进行交通网络分析时要考虑
到交通网络本身的特点。
首先，对于一定区域范围内庞大的交通网络要考虑它的存储结构，既要有利于网络分析
算法的实现，又能够在节约存储空间的前提下根据需要扩充数据，对交通网络进行综合分析。
网络的存储方法很多如邻接矩阵、关联矩阵、邻接表等，根据存储结构的设计可以将传统的
方法进行适当改进。
然后是网络搜索，主要依据求解单源点间最短路径的戴克斯徒拉算法思想，同样也可以
对其进行优化改进以提高效率。根据实际应用的需要，首先将网络边的权值设为两结点间的
距离，并定义沿着起点到终点的方向为空间有效方向，相反的方向为无效方向；然后赋给网
络边、结点相应的字段值，并定义站点、拐点、桥梁等特殊地物的属性，最后通过具体的程
序设计来实现搜索过程。
就本例而言，如果在存储结构、算法设计上都比较合理的话，对于包括县道以上所有级别的
道路情况，选择一个省范围内的一条最短路径，从条件输入完成开始到搜索完成，在微机上
运行时间一般在1分钟以内。在常用的地理信息系统软件中大多数都提供了菜单式的路径
分析命令，往往只需要使用者确定路径有效方向、权重字段以及起始点位置等，使用起来快
捷方便，但其结果不考虑地形、建筑物、人流、物流等外在因素的影响，过于理想化