10.2 最短路径与选址问题

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,2,节 最短路径与选址问题,最短路径问题,选址问题,1,对于许多地理问题，当它们被抽象为图论意义下的网络图时，问题的核心就变成了网络图上的优化计算问题。其中，最为常见的是关于路径和顶点的优选计算问题。,在路径的优选计算问题中，最常见的是最短路径问题；而在顶点的优选计算问题中，最为常见的是中心点和中位点选址问题。,2,“纯距离”意义上的最短路径,例如，,需要运送一批物资从一个城市到另一个城市，选择什么样的运输路线距离最短？,“经济距离”意义上的最短路径,例如，某公司在10大港口,C,1,，,C,2,，,C,10,设有货栈，从,C,i,到,C,j,之间的直接航运价格，是由市场动态决定的。如果两个港口之间无直接通航路线，则通过第三个港口转运。那么，各个港口之间最廉价的货运线路是什么？,一、最短路径问题,（一）最短路径的含义,3,“时间”意义上的最短路径,例如，某家经营公司有一批货物急需从一个城市运往另一个城市，那么，在由公路、铁路、河流航运、航空运输等,4,种运输方式和各个运输线路所构成的交通网络中，究竟选择怎样的运输路线最节省时间？,以上,3,类问题，都可以抽象为同一类问题，即赋权图上的最短路径问题。,不同意义下的距离都可以被抽象为网络图中边的权值。,权这种权值既可以代表“纯距离,”，又可以代表“经济距离,”，也可以代表“时间距离,”。,4,（二）,最短路径的算法,标号法,1959年,E.W.Dijkstar,提出的标号法是最短路径问题最好的求解方法,。,标号法优点,不仅可以求出起点到终点的最短路径及其长度，而且可以求出起点到其他任何一个顶点的最短路径及其长度,；,同时适用于求解有向图或无向图上的最短路径问题。,.,5,标号法的基本思想,设,G,是一个赋权有向图，即对于图中的每一条边，都赋予了一个权值。在图,G,中指定两个顶点，确定为起点和终点，不妨设,v,1,为起点，,v,k,为终点。,首先,从,v,1,开始，给每一个顶点标一个数，称为标 号。这些标号，又进一步区分为,T,标号和,P,标号两种类型。其中，每一个顶点的,T,标号表示从起点,v,1,到该点的最短路径长度的上界，这种标号为临时标号；,P,标号表示从,v,1,到该点的最短路长度，这种标号为固定标号。,在最短路径计算过程中，对于已经得到,P,标号的顶点，不再改变其标号；对于凡是没有标上,P,标号的顶点，先给它一个,T,标号；算法的每一步就是把顶点的,T,标号逐步修改，将其变为,P,标号。,那么，最多经过,k,-1,步，就可以求得到从起点,v,1,到每一个顶点的最短路径及其长度。,6,标号法具体计算步骤,如果刚刚得到,P,标号的点是,v,i,，,那么，对于所有这样的点,将其,T,标号修改为：,min,T,(,v,j,)，,P,(,v,i,)+,w,ij,。,若,G,中没有,T,标号，则停止。否则，把点 的,T,标号修改为,P,标号，然后再转入,。 其中， 满足,开始，先给,v,1,标上,P,标号,P,(,v,1,) 0，,其余各点标上,T,标号,T,(,v,j,)+（,j,1）。,7,例1,：在图10.2.1所示的赋权有向图中，每一个顶点,v,i,（,i,=1，2，,n,）,代表一个城镇；每一条边代表相应两个城镇之间的交通线，其长度用边旁的数字表示。试求城镇,v,1,到,v,7,之间的最短路径。,图10.2.1 赋权有向交通网络图,8,解,：首先给,v,1,标上,P,标号,P,(,v,1,)=0，,表示从,v,1,到,v,1,的最短路径为零。其他点(,v,2,，,v,3,，,v,7,),标上,T,标号,T,(,v,j,)+（,j,2，3，7）。,第,1,步,：,v,1,是刚得到,P,标号的点。因为(,v,1,，,v,2,)，(,v,1,，,v,3,)，(,v,1,，,v,4,),E,，,而且,v,2,，,v,3,，,v,4,是,T,标号，所以修改这,3,个点的,T,标号为,T,(,v,2,)min,T,(,v,2,)，,P,(,v,1,)+,w,12,min +，0+22,T,(,v,3,)min,T,(,v,3,)，,P,(,v,1,)+,w,13, min +，0+55,T,(,v,4,)min,T,(,v,4,)，,P,(,v,1,)+,w,14, min +，0+33,在所有,T,标号中，,T,(,V,2,)2,最小，于是令,P,(,V,2,)2。,9,第,2,步,：,v,2,是刚得到,P,标号的点。因为(,v,2,，,v,3,)，(,v,2,，,v,6,),E,，,而且,v,3,v,6,是,T,标号，故修改,v,3,和,v,6,的,T,标号为,T,(,v,3,)min,T,(,v,3,)，,P,(,v,2,)+,w,23,min5，2+24,T,(,v,6,)min,T,(,v,6,)，,P,(,v,2,)+,w,26,min+，2+79,在所有的,T,标号中，,T,(,v,4,)3,最小，于是令,P,(,v,4,)3。,10,第,3,步,：,v,4,是刚得到,P,标号的点。因为(,v,4,，,v,5,),E,，,而且,v,5,是,T,标号，故修改,v,5,的,T,标号为,T,(,v,5,)min,T,(,v,5,)，,P,(,v,4,)+,w,45,min+，3+58,在所有的,T,标号中，,T,(,v,3,)4,最小，故令,P,(,v,3,)4。,11,第,4,步：,v,3,是刚得到,P,标号的点。因为(,v,3,，,v,5,)，(,v,3,，,v,6,),E,，,而且,v,5,和,v,6,为,T,标号，故修改,v,5,和,v,6,的,T,标号为,T,(,v,5,)min,T(v,5,)，P(v,3,)+w,35,min8，4+37,T,(,v,6,)min,T,(,v,6,)，,P,(,v,3,)+,w,36,min9，4+59,在所有的,T,标号中，,T,(,v,5,)7,最小，故令,P,(,v,5,)7。,12,第,5,步：,v,5,是刚得到,P,标号的点。因为(,v,5,，,v,6,)，(,v,5,，,v,7,),E,，,而且,v,6,和,v,7,都是,T,标号，故修改它们的,T,标号为,T,(,v,6,)min,T,(,v,6,)，,P,(,v,5,)+,w,56,min9，7+1= 8,T,(,v,7,)min,T,(,v,7,)，,P,(,v,5,)+,w,57,min+，7+7=14,在所有,T,标号中，,T,(,v,6,)8,最小，于是令：,P,(,v,6,)8。,13,第,6,步：,v,6,是刚得到,P,标号的点。因为(,v,6,，,v,7,),E,，,而且,v,7,为,T,标号，故修改它的,T,标号为,T,(,v,7,)min,T,(,v,7,)，,P,(,v,6,)+,w,67,min14，8+5=13,目前只有,v,7,是,T,标号，故令：,P,(,v,7,)13。,从城镇,v,1,到,v,7,之间的最短路径为(,v,1,，,v,2,，,v,3,，,v,5,，,v,6,，,v,7,)，,最短路径长度为13。,14,二、选址问题,选址问题，是现代地理学研究的主要问题之一。选址问题涉及人类生产、生活、文化、娱乐等各个方面。,选址问题的数学模型取决于两个方面的条件,：,可供选址的范围、条件；怎样判定选址的质量。,本节的讨论仅限于选址的范围是一个地理网络，而且选址位置位于网络图的某一个或几个顶点上。,对这样的选址问题，根据其选址的质量判据，可以将其归纳为求网络图的中心点与中位点两类问题。,15,（一）,中心点选址问题,例,：某县要在其所辖的,6,个乡镇之一修建一个消防站，为,6,个乡镇服务，要求消防站至最远乡镇的距离达到最小。,中心点选址问题的质量判据,使最佳选址位置所在的顶点的最大服务距离为最小。,中心点选址问题适宜于医院、消防站点等一类服务设施的布局问题。,16,设,G,（,V,，,E,）,是一个无向简单连通赋权图，连接两个顶点的边的权值代表它们之间的距离，对于每一个顶点,v,i,，,它与各个顶点之间的最短路径长度为,d,i,1,，,d,i,2,，,d,in,。,这些距离中的最大数称为顶点,v,i,的最大服务距离，记为,e,(,v,i,)。,那么，中心点选址问题，就是求网络图,G,的中心点 ，使得,中心点选址问题的数学描述,17,例,2,：假设某县下属的,6,个乡镇及其之间公路联系如图所示。每一顶点代表一个乡镇；每一条边代表连接两个乡镇之间的公路，每一条边旁的数字代表该条公路的长度。现在要设立一个消防站，为全县的,6,个乡镇服务。试问该消防站应该设在哪一个乡镇（顶点）？,图10.2.2,18,解,：,第,1,步：,用标号法求出每一个顶点,v,i,至其他各个顶点,v,j,的最短路径长度,d,ij,（,i,，,j, 1，2，6），,并将它们写成如下的距离矩阵,19,第,2,步：,求每一个顶点的最大服务距离。显然，它们分别是矩阵,D,中各行的最大值，即：,e,(,v,1,)6，,e,(,v,2,)7，,e,(,v,3,)6，,e,(,v,4,)7，,e,(,v,5,)6，,e,(,v,6,)7。,第,3,步：,判定。因为,e,(,v,1,),e,(,v,3,),e,(,v,5,)min,e,(,v,i,)6，,所以,v,1,，,v,3,，,v,5,都是中心点。也就是说，消防站设在,v,1,，,v,3,，,v,5,中任何一个顶点上都是可行的。,20,中位点选址问题的质量判据,使最佳选址位置所在的顶点到网络图中其他各个顶点的最短路径距离的总和（或者以各个顶点的载荷加权求和）达到最小。,（二）中位点选址问题,21,中位点选址问题的数学描述,设,G,（,V,，,E,）,是一个简单连通赋权无向图，连接两个顶点的边的权值为该两顶点之间的距离；对于每一个顶点,v,i,（,i,1，2，,n,），,有一个正的负荷,a,(,v,i,)，,而且它与其他各顶点之间的最短路径长度为,d,i,1,，,d,i,2,，,d,in,。,那么，中位点选址问题，就是求图,G,的中位点 ，使得,22,例,3：某县下属,7,个乡镇，各乡镇所拥有的人口数,a,(,v,i,)（,i,=1，2，7），,以及各乡镇之间的距离,w,ij,（,i,，,j,=1，2，7）,如图所示。现在需要设立一个中心邮局，为全县所辖的,7,个乡镇共同服务。问该中心邮局应该设在哪一个乡镇（顶点）？,图10.2.3,23,解：,第,1,步：,用标号法求出每一个顶点,v,i,至其他各个顶点,v,j,的最短路径长度,d,ij,（,i,，,j, 1，2，7），,并将其写成如下距离矩阵,24,第,2,步：,以各顶点的载荷（人口数）加权，求每一个顶点至其他各个顶点的最短路径长度的加权和,25,第,3,步：判断。因为,所以，,v,3,和,v,4,都是图10.2.3的中位点,。,即：中心邮局设在点,v,3,或点,v,4,都是可行的。,26,