第二节 最短路径与选址问题

当地理系统中的地理事物及其之间的相互联系被抽象为地理网络图时， 许多地理系统分析问题就转化为图的计算问题，其中最为常见的是路径与顶点的计算。在路径计算中最为常用的是最短路径问题；而在顶点的计算中最为常见的是中心点与中位点的计算问题。目前，对于这些问题，图论研究已给我们提供了一些比较成熟的算法，下面分别作一简单介绍。

一、最短路径问题

最短路径问题，是地理系统网络分析中的一个重要问题之一，这一问题的研究不但具有重大的理论意义，而且具有重要的应用价值。交通网络结构的分析，交通运输线路（公路、铁路、河流航运线、航空线、管道运输线路等)的选择，通讯线路的建造与维护，运输货流的最小成本分析，城市公共交通网络的规划等，都有直接应用的价值。

（一)最短路径的含义

在地理系统的网络分析中，最短路径可以代表多种不同的含义。一般而言，它主要指以下三个方面的含义：

1. “纯距离”意义上的最短路径。例如，某旅行者想要乘汽车沿着一个国家或者地区的公路交通网络中的某一条线路，从一个城市到达另一个城市，那么这个旅行者就要考虑究竟沿怎样的路线（可以不是直达的线路)行进的距离最短？显然，这里所谓的距离是指实际的里程数，即“纯距离”。

2. “经济距离”意义上的最短路径。例如，某公司在世界上某 10 大港口 C1、C2、⋯、C1 均设有货栈，为了更好地适应市场供需的形势，经常要在各港口之间运送各类货物。从 Ci 到 Cj 之间的直接航运价格，可以从市场动态中得到。如果两个港口之间无直接通航路线时，可以通过第三个港口转运。随着市场动态的变化，该公司的经理就希望求出任意两个港口之间最为廉价的运货线路，即两个港口之间最短的“经济距离”。

3. “时间”意义上的最短路径。例如，某家经营公司有一批货物急需从一个城市运往另一个城市，那么在由公路、铁路、河流航运、航空运输等四种运输方式线路所构成的交通网络中，究竟选择怎样的送货路线（运输方式不限)最节省时间，即“时间”意义上的距离最短。

以上三例问题，我们都可以将其抽象为一类问题，即赋权有向图上的最短路径问题。在这里，不同意义的距离都被抽象为网络图中边的权数。自然， 这种权即可以代表“纯距离”，又可以代表“经济距离”，也可以代表“时间距离”。针对不同的问题，其距离（权数)和最短路径的含义可以不同。

（二)最短路径的算法

关于最短路径问题，目前为人们所公认的最好求解方法，是 1959 年由E.W.Dijkstar 提出的标号法。之所以被称为标号法，是由于在这个方法实施的过程中，对网络图中每一个顶点都对应一个数（或几个数)，这个数就称之为该顶点的标号。这个方法的一个突出优点是：它不仅求出了起点到终点的最短路径及其长度，而且求出了起点到图中其它各个顶点的最短路径及其长度。更值得一提的是，这一算法同样也适用于求无向图上的最短路径问题。以下我们具体地介绍这一算法。

设 G＝（V，E)是一个赋权有向图，即对于图中的每一条边 e＝（vi，vj)

都赋有权值ωij。在图 G 中指定两个顶点，确定为起点和终点，不妨设 vi 为起点，vp 为终点。标号法的基本思想是：首先从 v1 开始，给每一个顶点记一个数（称为标号)，标号分 T 标号和 P 标号两种，T 标号表示从起点 v1 到这一点的最短路权的上界，称为临时标号；P 标号表示从 v1 到该点的最短路权， 称为固定标号。已得到 P 标号的顶点不再改变，凡是没有标上 P 标号的顶点， 标上 T 标号。算法的第一步就是把某一顶点的 T 标号改变为 P 标号。那么， 最多经过 P-1 步，就可以得到从起点 v1 到每一个顶点的最短路径。其具体计算步骤如下：

开始，先给 v1 标上 P 标号 P（v1)＝0，其余各点标上 T 标号 T（vj)＝+

∞（j≠1)

1. 对于刚刚得到 P 标号的点 vi，考虑所有这样的点 vj，使（vi，vj)∈E， 而且 vj 的标号是 T 标号，然后修改 vj 的 T 标号为 min[T（vj)，P（vj)＋ωij]。

2. 若 G 中没有 T 标号，则停止。否则把点 vj0 的 T 标号修改为 P 标号， 然后再转入（1)。其中 vj0 满足：

T（vj0)=minT（vj)

vj0 是 T 标号。

例：在网络图 7-5 中，边旁的数字表示该边的权。求从 v1 到 v7 的最短路径。

开始，首先给 v1 标上 P 称号 P（v1)=0，表示从 v1 到 v1 的最短路权为零。其它点（v2，⋯，v7)标上 T 标号 T（vj)＝＋∞（j=2，3，⋯，7)。

第一步：①因为（v1，v2)，（v1，v3)，（v1，v4)∈E，而且 v2，v3，v4 是 T 标号，则修改这三个点的 T 标号为：

T（v2)=min[T（v2)，P（v1)+ω12]=min[+∞，0+2]=2

T（v3)=min[T（v3)，P（v1)+ω13]=min[+∞，0+5]=5 T（v4)=min[T（v4)，P（v1)+ω14]=min[+∞，0+3]=3

②在所有 T 标号中，T（v2)=2 最小，于是令 P（v2)=2。

第二步：①v2 是刚得到 P 标号的点，故考察 v2。因为（v2，v3)，（v2， v6)∈E，而且 v3，v6 是 T 标号，故修改 v3、v6 的 T 标号为

T（v3)=min[T（v3)，P（v2)+ω23]=min[5，2+2]=4 T（v6)=min[T（v6)，P（v2)+ω26]=min[∞，2+7]=9

②在图 G 中的所有 T 标号中，T（v4)=3 最小，于是令 P（v4)=3。

第三步：①考察 v4，因为（v4，v5)∈E，而且 v5 是 T 标号，故修改 v5 的 T 标号：

（v5)=min[T（v5)，P（v4)+ω45]=min[+∞，3+5]=8

②在图 G 中的所有 T 标号中，T（v3)=4 最小，故令 P（v3)=4。

第四步：①考察 v3，因为（v3，v5)，（v3，v6)∈E，而且 v5、v6 为 T 标号，故修改 v5、v6 的 T 标号为：

T（v5)=min[T（v5)，P（v3)+ω35]=min[8，4+3]=7 T（v6)=min[T（v6)，P（v3)+ω36]=min[9，4+5]=9

②在所有的 T 标号中，T（v5)=7，令 P（v5)=7。

第五步：①考察 v5，（v5，v6)，（v5，v7)∈E，而且 v6 和 v7 都是 T 标号，故修改 v6、v7 的 T 标号：

T（v6)=min[T（v6)，P（v5)+ω56]=min[9，7+1]=8 T（v7)=min[T（v7)，P（v5)+ω57]=min[∞，7+7]=14

②在所有 T 标号中，T（v6)=8 最小，令 P（v6)=8。

第六步：①考察 v6，（v6，v7)∈E，而且 v7 为 T 标号，故修改 v7 的 T 标号：

T（v7)=min[T（v7)，P（v6)+ω67]=min[14，8+5]=13。

②令 P（v7)=13

所以从 v1 到 v7 的最短路径为（v1，v2，v3，v5，v6，v7)，最短路径长度为 13。

二、选址问题

选址问题，是当代地理学三大方向之一——区位论研究的主要理论与应用课题之一。选址问题涉及人类生产、生活、文化、娱乐等各个方面。例如， 城市商业区、生活区、工厂、仓库、车站、机场、消防站点、文化娱乐场所等布局问题，都是选址问题。选址问题的数学模型取决于可供选址的范围， 以及怎样判定选址的质量两个方面的条件。由于存在大量的各种各样的选址问题，所以有关文献中也有各种各样的选址问题的数学模型及求解方法。但是，我们这里讨论的仅限于选址的范围是一个网络图，而且选址位置必须位于网络图的某一个或几个顶点上（当然亦可以位于一条边的某一个位置上， 关于这方面的讨论，有兴趣的读者可以参看有关的图论著作)。对这样的选址问题，根据其选址的质量判据，我们又可以将其归纳为求网络图的中心点与中位点两类问题。

（一)中心点选址问题

中心点选址问题的质量判据，是使最佳选址位置所在的顶点与图中其它顶点之间的最大距离达到最小。这类选址问题适宜于医院、消防站点等一类服务设施的布局问题。例如，某县要在其所辖的六个乡镇之一修建一个消防站，为六个乡镇服务，要求消防站至最远乡镇的距离达到最小。这就是选址问题，实际上就是求网络图的中心点问题。其数学描述为：

设 G＝（V，E)（其中 V=｛v1，v2，⋯，vn｝，E=｛e1，e2，⋯，en｝是一个无向简单连通赋权图)，联接两个顶点的边的权值代表该两顶点之间的距离，对于每一个顶点 vi，它与各顶点之间的最短路径长度为 di1，di2，⋯， din。这几个距离中的最大数称为顶点 vi 的最大服务距离，记为 e（vi)。那么，中心点选址问题，就是求图 G 的中心点 vi0，使得

e（vi0)=min{e（vi)} （1)

假若上例中的六个乡镇及其之间的距离被抽象为图 7-6 所示的无向简单连通赋权圈，试问消防站点应设在哪一个乡镇，即哪一个顶点？

首先，用标号法求出每一个顶点 vi 至其它各顶点 vj 的最短路径长度 dij

（i，j＝1，2，⋯，6)，写出距离矩阵：

 21 22 23 24 25 26  

 41 42 43 44 45 46  

52 53 54 55 56  

其次求距离矩阵中每行的最大值得 e（v1)=6，e（v2)=7，e（v3)=6，e（v4)=7， e（v5)=6，e（v6)=7。显然：e（v1)=e（v3)=e（v5)=min{e（vi)}=6。所以， 消防站应建在 v1，v3，v5 点所在的乡镇即可。

（二)中位点选址问题

中位点选址问题的质量判据，是使最佳选址位置所在的顶点到网络图中其它顶点的距离（亦可以是加权距离)总和达到最小。这类选址问题的数学描述为：

设 G＝（V，E)（其中 V＝｛v1，v2，⋯，vn｝，E＝｛e1，e2，⋯，en｝) 是一个简单连通赋权无向图，联结两个端点的边的权值为该两点之间的距离；对于每一个顶点 vi（i=1，2，⋯，n)，有一个正的负荷 a（vi)，而且它与其它各顶点之间的最短路径长度为：di1，di2，⋯，din ，那么，中位点选址问题就是求图 G 中的中位点 vi0，使得：

 n 

S( vi0 ) = min S(vi ) = min∑a(v j )d ij 

(2)

i i  j=1 

例如，某县下属七个乡镇，各乡镇所拥有的人口α（vi)（i＝1，2，⋯， 7)，以及各乡镇之间的距离ωij（i，j=1，2，⋯，7)如图 7-7 中所示，现要在七个乡镇之一建一个邮局，为全县所属的七个乡镇服务，试问哪一个乡镇所在地（图中的哪一个顶点)应该作为邮局的选址？显然，邮局的最佳应该是图 7-7 的中位点。

首先，用标号法求出每一个顶点 vi 至其它各个顶点 vj 的最短路径长度dij（i，j＝1，2，⋯，7)，得到距离矩阵：

 d11 d12 d13 d14 d15 d16 d17 

d d d d d d d 

 21 22 23 24 25 26 27 

d 31 d 32 d33 d 34 d35 d 36 d 37 

D = d 41 d 42 d43 d 44 d45 d 46 d 47  … .

 d d d d d d d 

 51 52 53 54 55 56 57 

d 61 d 62 d63 d 64 d65 d 66 d 67 

d d d d d d d 

 71 72 73 74 75 76 77 

 0 3 5 6.3 9.3 4.5 6 

 3 0 2 3.3 6.3 1.5 3 

 5 2 0 2 5 3.5 5 

 

=  6.3 3.3 2 0 3 1.8 3.3 

 9.3 6.3 5 3 0 4.8 6.3 

 

 4.5 1.5 3.5 1.8 4.8 0 1.5

 6 3 5 3.3 6.3 1.5 0 

由上述距离矩阵可以求得：

7

S( v1 ) = ∑a( v j )d1 j = 122.3

j=1

S( v2 ) = ∑a(vj )d2 j = 71.3

j=1

S( v3 ) = ∑a( v j )d 3 j = 69.5

J =1

S( v4 ) = ∑a(vj )d4 j = 69.5

j=1

S( v5 ) = ∑a(v j )d5 j = 108.5

j=1

S( v6 ) = ∑a(vj )d 6 j = 72.8

j=1

S( v7 ) = ∑a(vj )d7 j = 95.3

j=1

因此S(v3 ) = S(v4 ) = min{S( vi )}

 7 

= min∑a(v j )dij  = 69.5

i  j=1 

即 v3 和 v4 都是图 7-7 的中位点。所以邮局的最佳选址应该为 v3 或 v4。