短路径与选址问题课件.ppt

第二节第二节 最短路径与选址问题最短路径与选址问题 对于许多地理问题，当它们被抽象为图论意义下的网络图时，问题的核心就变成了网络图上的优化计算问题其中，最为常见的是关于路径和顶点的优选计算问题 在路径的优选计算问题中，最常见的是最最短短路路径径问问题题；而在顶点的优选计算问题中，最为常见的是中心点中心点和中位点中位点选址问题 《短路径与选址问题》PPT课件（1）“纯距离”意义上的最短路径 例如，需要运送一批物资从一个城市到另一个城市，选择什么样的运输路线距离最短？（2）“经济距离”意义上的最短路径 例如，某公司在10大港口C1，C2，…，C10设有货栈，从Ci到Cj之间的直接航运价格，是由市场动态决定的如果两个港口之间无直接通航路线，则通过第三个港口转运那么，各个港口之间最廉价的货运线路是什么？一、最短路径问题一、最短路径问题（一）最短路径的含义（一）最短路径的含义《短路径与选址问题》PPT课件 （3）“时间”意义上的最短路径 例如，某家经营公司有一批货物急需从一个城市运往另一个城市，那么，在由公路、铁路、河流航运、航空运输等四种运输方式和各个运输线路所构成的交通网络中，究竟选择怎样的运输路线最节省时间？ ◣以上三类问题，都可以抽象为同一类问题，即赋权图上的最短路径问题。

◣不同意义下的距离都可以被抽象为网络图中边的权值◣权——这种权值既可以代表“纯距离纯距离 ”，又可以代表“经济距离经济距离 ”，也可以代表“时间距时间距离离 ” 《短路径与选址问题》PPT课件（二）（二）最短路径的算法最短路径的算法n最短路径问题最好的求解方法：1959年，E．W．Dijkstar 提出的标号法标号法n标号法优点标号法优点 不仅可以求出起点到终点的最短路径及其长度，而且可以求出起点到其它任何一个顶点的最短路径及其长度； 同时适用于求解有向图或无向图上的最短路径问题n标号法的基本思想标号法的基本思想 设是一个赋权有向图，即对于图中的每一条边，都赋予了一个权值在图G中指定两个顶点，确定为起点和终点，不妨设为起点，为终点 《短路径与选址问题》PPT课件标号法的基本思想是：标号法的基本思想是： 首首先先v1从从开开始始，，给给每每一一个个顶顶点点标标一一个个数数，，称称为为标标号号这这些些标标号号，，又又进进一一步步区区分分为为T标标号号和和P标标号号两两种种类类型型其其中中，，每每一一个个顶顶点点的的T标标号号表表示示从从起起点点v1到到该该点点的的最最短短路路径径长长度度的的上上界界，，这这种种标标号号为为临临时时标标号号；；P标标号号表表示示从从v1到到该该点点的的最最短短路路长长度度，，这这种种标号为固定标号。

标号为固定标号 在在最最短短路路径径计计算算过过程程中中，，对对于于已已经经得得到到P标标号号的的顶顶点点，，不不再再改改变变其其标标号号；；对对于于凡凡是是没没有有标标上上P标标号号的的顶顶点点，，先先给给它它一一个个T标标号号；；算算法法的的每每一一步步就就是是把顶点的把顶点的T标号逐步修改，将其变为标号逐步修改，将其变为P标号那那么么，，最最多多经经过过k-1-1步步，，就就可可以以求求得得到到从从起起点点v1到到每一个顶点的最短路径及其长度每一个顶点的最短路径及其长度《短路径与选址问题》PPT课件▇ ▇ 标号法具体计算步骤标号法具体计算步骤 ① ① 如果刚刚得到P标号的点是vi，那么，对于所有这样的点 将其T标号修改为：min[T(vj)，P(vi)+wij] ②② 若G中没有T标号，则停止否则，把点 的T标号修改为P标号，然后再转入①其中， 满足： 开始，先给v1标上P标号P(v1)＝ 0，其余各点标上T标号T(vj)＝+∞（j≠1） 《短路径与选址问题》PPT课件例例1：在图10.2.1所示的赋权有向图中，每一个顶点vi（i=1，2，…，n）代表一个城镇；每一条边代表相应两个城镇之间的交通线，其长度用边旁的数字表示。

试求城镇v1到v7之间的最短路径 图图10.2.1 赋权有向交通网络图赋权有向交通网络图《短路径与选址问题》PPT课件解解： 首先给v1标上P标号P(v1)=0，表示从v1到v1的最短路径为零其它点(v2，v3，…，v7)标上T标号T(vj)＝+∞（j＝2，3，…，7）第一步第一步： ①① v1是刚得到P标号的点因为(v1，v2)，(v1，v3)，(v1，v4)∈E，而且v2，v3，v4是T标号，所以修改这三个点的T标号为： T(v2)＝min[T(v2)，P(v1)+w12]＝min[ +∞，0+2]＝2 T(v3)＝min[T(v3)，P(v1)+w13 ]＝ min[ +∞，0+5]＝5 T(v4)＝min[T(v4)，P(v1)+w14 ]＝ min[ +∞，0+3]＝3 ②② 在所有T标号中，T(V2)＝2最小，于是令P(V2)＝2《短路径与选址问题》PPT课件第二步第二步： ①① v2是刚得到P标号的点因为(v2，v3)，(v2，v6)∈E，而且v3, v6是T标号，故修改v3和v6的T标号为： T(v3)＝min[T(v3)，P(v2)+w23]＝min[5，2+2]＝4 T(v6)＝min[T(v6)，P(v2)+w26]＝min[+∞，2+7]＝9 ②② 在所有的T标号中，T(v4)＝3最小，于是令P(v4)＝3。

《短路径与选址问题》PPT课件第三步：第三步： ①① v4是刚得到P标号的点因为(v4，v5)∈E，而且v5是T标号，故修改v5的T标号为： T(v5)＝min[T(v5)，P(v4)+w45]＝min[+∞，3+5]＝8 ②② 在所有的T标号中，T(v3)＝4最小，故令P(v3)＝4《短路径与选址问题》PPT课件第四步：第四步： ①① v3是刚得到P标号的点因为(v3，v5)，(v3，v6)∈E，而且v5和v6为T标号，故修改v5和v6的T标号为： T(v5)＝min[T(v5)，P(v3)+w35]＝min[8，4+3]＝7 T(v6)＝min[T(v6)，P(v3)+w36]＝min［9，4+5]＝9 ②② 在所有的T标号中，T(v5)＝7最小，故令P(v5)＝7 《短路径与选址问题》PPT课件第五步：第五步： ①① v5是刚得到P标号的点因为(v5，v6)，(v5 ，v7)∈E，而且v6和v7都是T标号，故修改它们的T标号为： T(v6)＝min[T(v6)，P(v5)+w56]＝min[9，7+1]= 8 T(v7)＝min[T(v7)，P(v5)+w57]＝min[+∞，7+7]=14 ②② 在所有T标号中，T(v6)＝8最小，于是令：P(v6)＝8。

《短路径与选址问题》PPT课件第六步：第六步： ①① v6是刚得到P标号的点因为(v6，v7)∈E，而且v7为T标号，故修改它的T标号为： T(v7)＝min[T(v7)，P(v6)+w67]＝min[14，8+5]=13 ②② 目前只有v7是T标号，故令：P(v7)＝13 从城镇v1到v7之间的最短路径为(v1，v2，v3，v5，v6，v7)，最短路径长度为13 《短路径与选址问题》PPT课件二、选址问题二、选址问题 n选址问题，是现代地理学的分支学科——区位论区位论 研究的主要方向之一选址问题涉及人类生产、生活、文化、娱乐等各个方面n选址问题的数学模型取决于两个两个方面的条件 ：①可可供选址的范围、条件供选址的范围、条件；②怎样判定选址的质量怎样判定选址的质量n本节的讨论仅限于选址的范围选址的范围 是一个地理网络地理网络，而且选址位置选址位置 位于网络图的某一个或几个顶点顶点上 n对这样的选址问题，根据其选址的质量判据选址的质量判据，可以将其归纳为求网络图的中心点与中位点网络图的中心点与中位点 两类问题 《短路径与选址问题》PPT课件（一）（一）中心点选址问题中心点选址问题 例例：某县要在其所辖的六个乡镇之一修建一个消防站，为六个乡镇服务，要求消防站至最远乡镇的距离达到最小。

n中心点选址问题的质量判据：使最佳选址位置所在的顶点的最大服务距离为最小使最佳选址位置所在的顶点的最大服务距离为最小n中心点选址问题适宜于医院、消防站点等一类服务设施的布局问题 《短路径与选址问题》PPT课件 设G＝（V，E）是一个无向简单连通赋权图，连结两个顶点的边的权值代表它们之间的距离，对于每一个顶点vi，它与各个顶点之间的最短路径长度为di1，di2，…，din这些距离中的最大数称为顶点vi的最大服务距离，记为e(vi) 那么，中心点选址问题，就是求网络图G的中心点 ，使得 n中心点选址问题的数学描述中心点选址问题的数学描述 《短路径与选址问题》PPT课件例例2：假设某县下属的六个乡镇及其之间公路联系如图所示每一顶点代表一个乡镇；每一条边代表连接两个各乡镇之间的公路，每一条边旁的数字代表该条公路的长度现在要设立一个消防站，为全县的六个乡镇服务试问该消防站应该设在哪一个乡镇（顶点）？ 图图10.2.210.2.2《短路径与选址问题》PPT课件解解： 第第一一步步：：用标号法求出每一个顶点vi至其它各个顶点vj的最短路径长度dij（i，j ＝ 1，2，…，6），并将它们写成如下的距离矩阵：《短路径与选址问题》PPT课件 第第二二步步：：求每一个顶点的最大服务距离。

显然，它们分别是矩阵D中各行的最大值，即： 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都是中心点也就是说，消防站设在v1，v3，v5中任何一个顶点上都是可行的 《短路径与选址问题》PPT课件n中位点选址问题的质量判据： 使最佳选址位置所在的顶点到网络图中其使最佳选址位置所在的顶点到网络图中其它各个顶点的最短路径距离的总和（或者以各它各个顶点的最短路径距离的总和（或者以各个顶点的载荷加权求和）达到最小个顶点的载荷加权求和）达到最小二）中位点选址问题（二）中位点选址问题《短路径与选址问题》PPT课件n中位点选址问题的数学描述: 设G＝（V，E）是一个简单连通赋权无向图，连接两个顶点的边的权值为该两顶点之间的距离；对于每一个顶点vi（i＝1，2，…，n），有一个正的负荷a(vi)，而且它与其它各顶点之间的最短路径长度为di1，di2，…，din那么，中位点选址问题，就是求图G的中位点 ，使得： 《短路径与选址问题》PPT课件例例3：某县下属七个乡镇，各乡镇所拥有的人口数a(vi)（i=1，2，…，7），以及各乡镇之间的距离wij（i，j=1，2，…，7）如图所示。

现在需要设立一个中心邮局，为全县所辖的七个乡镇共同服务问该中心邮局应该设在哪一个乡镇（顶点）？ v1v3v4v5v6v762321.831.5v21.5a(v7)=4a(v5)=5a(v4)=1a(v1)=3a(v3)=7a(v6)=1a(v2)=2图10.2.3《短路径与选址问题》PPT课件解：解：第第一一步步：：用标号法求出每一个顶点vi至其它各个顶点vj的最短路径长度dij（i，j ＝ 1，2，…，7），并将其写成如下距离矩阵： 《短路径与选址问题》PPT课件 第第二二步步：：以各顶点的载荷（人口数）加权，求每一个顶点至其它各个顶点的最短路径长度的加权和： 《短路径与选址问题》PPT课件 第三步第三步：判断 因为 所以，v3和v4都是图10.2.3的中位点 即：中心邮局设在点v3或点v4都是可行的 《短路径与选址问题》PPT课件QhTlWoZr%u(x+B2E6H9KcOfRiUmXp!s&v)z0C3F7IaMdPgSkVnYq$t*x-A1D5G8JbNeQhTlWo#r%u(y+B2E6H9LcOfRjUmXp!s&w)z0C4F7IaMdPhSkVnZq$t*x-A2D5G8KbNeQiTlXo#r%v(y+B3E6I9LcOgRjUmYp!s&w)z1C4F7JaMdPhSkWnZq$u*x-A2D5H8KbNfQiTlXo#s%v(y0B3E6I9LdOgRjVmYp!t&w-z1C4G7JaMePhTkWnZr$u*x+A2E5H8KcNfQiUlXo#s%v)y0B3F6I9LdOgSjVmYq!t&w-z1D4G7JbMePhTkWoZr$u(x+A2E5H9KcNfRiUlXp#s&v)y0C3F6IaLdPgSjVnYq!t*w-z1D4G8JbMeQhTkWoZr%u(x+B2E5H9KcOfRiUmXp#s&v)z0C3F7IaLdPgSkVnYq$t*w-A1D5G8JbNeQhTlWo#r%u(y+B2E6H9LcOfRjUmXp!s&v)z0C4F7IaMdPgSkVnZq$t*x-A1D5G8KbNeQiTlWo#r%v(y+B3E6H9LcOgRjUmYp!s&w)z1C4F7JaMdPhSkWnZq$u*x-A2D5G8KbNfQiTlXo#r%v(y0B3E6I9LcOgRjVmYp!t&w)z1C4G7JaMePhSkWnZr$u*x+A2D5H8KcNfQiUlXo#s%v)y0B3F6I9LdOgRjVmYq!t&w-z1C4G7JbMePhTkWnZr$u(x+A2E5H8KcNfRiUlXp#s%v)y0C3F6IaLdOgSjVnYq!t*w-z1D4G8JbMeQhTkWoZr%u(x+B2E5H9KcNfRiUmXp#s&v)y0C3F7IaLdPgSjVnYq$t*w-A1D4G8NfRiUlXp#s%v)y0C3F6IaLdOgSjVnYq!t*w-z1D4G7JbMeQhTkWoZr$u(x+B2E5H9KcNfRiUmXp#s&v)y0C3F7IaLdPgSjVnYq$t*w-A1D4G8JbNeQhTlWoZr%u(y+B2E6H9KcOfRjUmXp!s&v)z0C3F7IaMdPgSkVnYq$t*x-A1D5G8JbNeQiTlWo#r%u(y+B3E6H9LcOfRjUmYp!s&w)z0C4F7JaMdPhSkVnZq$u*x-A2D5G8KbNeQiTlXo#r%v(y+B3E6I9LcOgRjUmYp!t&w)z1C4F7JaMePhSkWnZq$u*x+A2D5H8KbNfQiUlXo#s%v(y0B3F6I9LdOgRjVmYp!t&w-z1C4G7JaMePhTkWnZr$u*x+A2E5H8KcNfQiUlXp#s%v)y0B3F6IaLdOgSjVmYq!t*w-z1D4G7JbMeQhTkWoZr$u(x+B2E5H9KcNfRiUlXp#s&v)y0C3F6IaLdPgSjVnYq!t*w-A1D4G8JbMeQhTlWoZr%u(x+B2E6H9KcOfRiUmXp!s&v)z0C3F7IaMdPgSkVnYq$t*w-A1D5G8JbNeQhTlWo#r%u(y+B2E6H9LcOfRjUmXp!s&w)z0C4F7IaMdPhSkVnZq$t*x-A2D5G8KbNeQiTlXo#r%v(y+B3E6H9LcOgRjUmYp!s&w)z1C4F7JaMdPhSkWnZq$u*x-A2D5H8KbNfQiTlXo#s%v(y0B3E6I9LdOgRjVmYp!t&w-z1C4G7JaMePhTkWnZr$u*x+A2D5H8KcNfQiUlXo#s%v)y0B3F6I9LdOgSjVmYq!t&w-z1D4G7JbMePhTkWoZr$u(x+A2E5H9KcNfRiUlXp#s&v)y0C3F6IaLdOgSjVnYq!t*w-z1D4G8JbMeQhT#s%v)y0B3F6I9LdOgSjVmYq!t&w-z1D4G7JbMePhTkWoZr$u(x+A2E5H9KcNfRiUlXp#s%v)y0C3F6IaLdOgSjVnYq!t*w-z1D4G8JbMeQhTkWoZr%u(x+B2E5H9KcOfRiUmXp#s&v)z0C3F7IaLdPgSkVnYq$t*w-A1D4G8JbNeQhTlWoZr%u(y+B2E6H9KcOfRjUmXp!s&v)z0C4F7IaMdPgSkVnZq$t*x-A1D5G8KbNeQiTlWo#r%v(y+B3E6H9LcOgRjUmYp!s&w)z0C4F7JaMdPhSkVnZq$u*x-A2D5G8KbNfQiTlXo#r%v(y0B3E6I9LcOgRjVmYp!t&w)z1C4G7JaMePhSkWnZr$u*x+A2D5H8KbNfQiUlXo#s%v(y0B3F6I9LdOgRjVmYq!t&w-z1C4G7JbMePhTkWnZr$u(x+A2E5H8KcNfRiUlXp#s%v)y0C3F6IaLdOgSjVmYq!t*w-z1D4G7JbMeQhTkWoZr$u(x+B2E5H9KcNfRiUmXp#s&v)y0C3F7IaLdPgSjVnYq$t*w-A1D4G8JbNeQhTlWoZr%u(y+B2E6H9KcOfRiUmXp!s&v)z0C3F7IaMdPgSkVnYq$t*x-A1D5G8JbNeQiTlWo#r%u(y+B3E6H9LcOfRjUmYp!s&w)z0C4F7JaMdPhSkVnZq$t*x-A2D5G8KbNeQiTlXo#r%v(y+B3E6I9LcOgRjUmYp!t&w)z1C4F7JaMePhSkWnZq$u*x+A2D5H8KbNfQiUlXo#s%v(y0B3E6I9LdOgRjVmYp!t&w-z1C4G7JaMePhTkWnZr$u*x+A2E5H8KcNfQiUlXp#s%v)y0B3F6IaLdOgWnZq$u*x+A2D5H8KbNfQiTlXo#s%v(y0B3E6I9LdOgRjVmYp!t&w-z1C4G7JaMePhTkWnZr$u*x+A2E5H8KcNfQiUlXp#s%v)y0B3F6IaLdOgSjVmYq!t&w-z1D4G7JbMePhTkWoZr$u(x+A2E5H9KcNfRiUlXp#s&v)y0C3F6IaLdPgSjVnYq!t*w-A1D4G8JbMeQhTlWoZr%u(x+B2E6H9KcOfRiUmXp#s&v)z0C3F7IaLdPgSkVnYq$t*w-A1D5G8JbNeQhTlWo#r%u(y+B2E6H9LcOfRjUmXp!s&w)z0C4F7IaMdPhSkVnZq$t*x-A1D5G8KbNeQiTlWo#r%v(y+B3E6H9LcOgRjUmYp!s&w)z1C4F7JaMdPhSkWnZq$u*x-A2D5H8KbNfQiTlXo#s%v(y0B3E6I9LcOgRjVmYp!t&w)z1C4G7JaMePhSkWnZr$u*x+A2D5H8KcNfQiUlXo#s%v)y0B3F6I9LdOgSjVmYq!t&w-z1D4G7JbMePhTkWoZr$u(x+A2ELcOgRjVmYp!t&w)z1C4G7JaMePhSkWnZr$u*x+A2D5H8KcNfQiUlXo#s%v)y0B3F6I9LdOgSjVmYq!t&w-z1C4G7JbMePhTkWnZr$u(x+A2E5H8KcNfRiUlXp#s%v)y0C3F6IaLdOgSjVnYq!t*w-z1D4G8JbMeQhTkWoZr%u(x+B2E5H9KcOfRiUmXp#s&v)y0C3F7IaLdPgSjVnYq$t*w-A1D4G8JbNeQhTlWoZr%u(y+B2E6H9KcOfRjUmXp!s&v)z0C4F7IaMdPgSkVnZq$t*x-A1D5G8JbNeQiTlWo#r%u(y+B3E6H9LcOfRjUmYp!s&w)z0C4F7JaMdPhSkVnZq$u*x-A2D5G8KbNfQiTlXo#r%v(y0B3E6I9LcOgRjVmYp!t&w)z1C4F7JaMePhSkWnZq$u*x+A2D5H8KbNfQiUlXo#s%v(y0B3F6I9LdOgRjVmYq!t&w-z1G8KbNfQiTlXo#r%v(y+B3E6I9LcOgRjUmYp!t&w)z1C4F7JaMePhSkWnZq$u*x+A2D5H8KbNfQiUlXo#s%v(y0B3F6I9LdOgRjVmYq!t&w-z1C4G7JaMePhTkWnZr$u*x+A2E5H8KcNfQiUlXp#s%v)y0B3F6IaLdOgSjVmYq!t*w-z1D4G7JbMeQhTkWoZr$u(x+B2E5H9KcNfRiUmXp#s&v)y0C3F6IaLdPgSjVnYq!t*w-A1D4G8JbMeQhTlWoZr%u(x+B2E6H9KcOfRiUmXp!s&v)z0C3F7IaMdPgSkVnYq$t*x-A1D5G8JbNeQhTlWo#r%u(y+B2E6H9LcOfRjUmXp!s&w)z0C4F7IaMdPhSkVnZq$t*x-A2D5G8KbNeQiTlXo#r%v(y+B3E6I9LcOgRjUmYp!t&w)z1C4F7JaMdPhSkWnZq$u*x-A2D5H8KbNfQiTlXo#s%v(y0B3E6I9LdOgRjVmYp!t&w-z1C4G7JaMePhTkWnZr$u*x+A2E5H8KcNfQiUlXo#s%vC4F7JaMdPhSkWnZq$u*x-A2D5H8KbNfQiTlXo#s%v(y0B3E6I9LdOgRjVmYp!t&w-z1C4G7JaMePhSkWnZr$u*x+A2D5H8KcNfQiUlXo#s%v)y0B3F6I9LdOgSjVmYq!t&w-z1D4G7JbMePhTkWoZr$u(x+A2E5H9KcNfRiUlXp#s&v)y0C3F6IaLdOgSjVnYq!t*w-z1D4G8JbMeQhTkWoZr%u(x+B2E5H9KcOfRiUmXp#s&v)z0C3F7IaLdPgSkVnYq$t*w-A1D5G8JbNeQhTlWoZr%u(y+B2E6H9KcOfRjUmXp!s&v)z0C4F7IaMdPgSkVnZq$t*x-A1D5G8KbNeQiTlWo#r%v(y+B3E6H9LcOgRjUmYp!s&w)z1C4F7JaMdPhSkVnZq$u*x-A2D5G8KbNfQiTlXo#r%v(y0B3E6I9LcOgRjVmYp!t&w)z1C4G7JaMePhSkWnZr$u*x+A6H9LcOfRjUmYp!s&w)z0C4F7JaMdPhSkVnZq$u*x-A2D5G8KbNfQiTlXo#r%v(y0B3E6I9LcOgRjVmYp!t&w)z1C4G7JaMePhSkWnZr$u*x+A2D5H8KbNfQiUlXo#s%v(y0B3F6I9LdOgRjVmYq!t&w-z1C4G7JbMePhTkWnZr$u(x+A2E5H8KcNfRiUlXp#s%v)y0C3F6IaLdOgSjVmYq!t*w-z1D4G7JbMeQhTkWoZr$u(x+B2E5H9KcNfRiUmXp#s&v)y0C3F7IaLdPgSjVnYq$t*w-A1D4G8JbNeQhTlWoZr%u(x+B2E6H9KcOfRiUmXp!s&v)z0C3F7IaMdPgSkVnYq$t*x-A1D5G8JbNeQiTlWo#r%u(y+B3E6H9LcOfRjUmYp!s&w)z0C4F7JaMdPhSkVnZq$t*x-A2D5G8KfRiUmXp!s&v)z0C3F7IaMdPgSkVnYq$t*x-A1D5G8JbNeQiTlWo《短路径与选址问题》PPT课件。