最短路径与选址问题.ppt

最短路径和布局问题，最短路径问题的布局问题，对于很多地理问题，如果被抽象化为图解意义上的网络地图的话，问题的核心就成为网络地图上的最佳计算问题。 其中最常见的是关于路径和顶点的最佳计算问题。 在路径的优选计算问题中，最常见的是最短路径问题顶点的最佳计算问题中最常见的是中心点和中点的选择问题。 “纯粹的距离”意义上的最短路径，比如说，需要从一个城市向另一个城市运送物资，什么样的运输路径最短？ “经济距离”意义上的最短路径，例如，某公司在10个港口的C1、C2、C10上设置货场，Ci到Cj之间的直接航运价格由市场动态决定。 如果两个港口之间没有直接通航路线，就通过第三个港口运输。 那么，各港口之间最便宜的货物输送路径是什么？一、最短路径问题、(一)最短路径的意思、“时间”的意思的最短路径，例如，一家经营公司需要从一个城市运送货物，由道路、铁路、河流航运、航空运输等四种输送方式和各输送路径构成的交通网络中以上三种问题都可以抽象化为同一种问题，即权利地图上的最短路径问题。 不同意义上的距离可以抽象为网络图中边的权重。 权的权重可以表示“纯距离”和“经济距离”两者，也可以表示“时间距离”。 (2)最短路径的算法，标签法1959年E.W.Dijkstar提出的标签法是最短路径问题的最佳解决方法。 编码法的优点不仅适合于解决从起点到终点的最短路径及其长度，也适合于解决从起点到任何其他顶点的最短路径及其长度的有向图或无向图上的最短路径问题。标记法的基本思想是把g作为有权利的有向图，也就是说在图中的每一边都给予了权利值。 在图g中指定两个顶点来确定起点和终点，但是也可以将v1作为起点，将vk作为终点。 首先，从v1开始，按顶点编号，称为标签。 这些标签还分为t标签和p标签两种。 此处，各顶点t标签表示从起点v1到该点的最短路径长度的上限，该标签是临时标签，p标签表示从v1到该点的最短长度，该标签是固定标签。 对于在最短路径计算过程中已经得到p标签的顶点，标签不变，对于没有标签为p的顶点，首先标记t的算法的每个步骤是逐渐修改顶点的t标签，使其成为p标签。 并且，通过最大经过k-1步，可以求出从起点v1到各顶点的最短路径及其长度。 标签法的具体的计算顺序，如果刚得到p标签的点是vi的话，就对所有这样的点将t标签修正为minT(vj )，P(vi) wij。 如果g上没有t标志就停止。 否则，将点的t标记修正为p标记后转移到。 在此，满足，首先，在v1上加p标记P(v1)=0，在剩下的各点上加t标记T(vj)=(j1 )。 例1 :在图10.2.1所示的授权有向图表中，顶点VI (I=1，2，n )代表一个城市，其中每条边代表两个对应的城市之间的相交线，并且其长度用一个边旁边的数字表示。 求一下镇上从v1到v7的最短路径吧。 赋予图10.2.1交通网络图权利，解：首先在v1上标记P(v1)=0，表示从v1到v1的最短路径为0。 在其他点(v2、v3、v7 )上加t标记T(vj)=(j=2,3、3、7 )。 步骤1:v1是刚得到p的标签这一点。由于(v1，v2 )、(v1，v3 )、(v1，v4)E以及v2、v3、v4是t标签，所以修改了这三点的t标签是T(v2)=minT(v2 )，P(v1) w12=min ，02 =2t (v3 )=min 在所有的t标签中，T(V2)=2是最小的，因此，P(V2)=2是最小的。 步骤2:v2是刚得到p的标签这一点。 由于(v2、v3)、(v2、v6)E和v3、v6是t标签，所以修改后的v3和v6的t标签是T(v3)=minT(v3)、P(v2) w26=min ，2=4t(v6)=mint(v6)、p (v2)。 步骤3:v4是刚得到p的标签这一点。 由于(v4、v5 )MMMR和v5是t标签，所以修正了V5的t标签在所有的t标签中T(v3)=4是最小的，所以设P(v3)=4。 步骤4:v3是刚得到p的标签。 因为v3、v5、v3、v6和v5和v6是t标签，所以修改了v5和v6的t标签是T(v5)=minT(v5)，p (v3) w 35 =min 8，4=7t (v6)=min t (v6)，p (v3)。 步骤5:v5是刚得到p的标签。 由于(v5，v6 )、(v5，v7)E以及v6和v7都是t标签，所以修改了它们的t标签是T(v6)=minT(v6 )，p (V5 ) w56 =min 9，71 =8t (V7 )=min t (V7 )，p (p )。 步骤6:v6是刚得到p的标签这一点。 因为(v6、v7 )MMMMR而且v7是t标签，所以修正该t标签的只有T(v7)=minT(v7 )、p (V6 ) w67 =min 14，85 =13现在V7是t标签，所以P(v7)=13。 从镇v1到v7的最短路径是(v1，v2，v3，v5，v6，v7)，最短路径长度是13。 二、布局问题、布局问题是现代地理学研究的主要问题之一。 布局问题涉及人类的生产、生活、文化、娱乐等各个方面。 立地问题的数学模型取决于两方面的条件：可以立地的范围、条件如何判定立地的质量。 本节的讨论是地理网络，且布局位置仅限于网络图的一个或多个顶点。 对于这种布局问题，根据该布局的质量标准，可以总结出网络图的中心点和中点两种问题。 (1)中心点的布局问题，如：某县在其管辖的6个乡镇之一建设消防站，要求为6个乡镇服务，从消防站到最远的乡镇的距离最小。 中心点布局问题的质量标准使最佳布局位置顶点的最大服务距离最小化。 中心点的布局问题适合医院、消防网站等服务设施的配置问题。 将G=(V，e )设为无方向单纯连接加权图，连接两个顶点的边的权重表示它们的距离，对于每个顶点vi，将与各自顶点的最短路径长度设为di1、di2、din。 这些距离的最大数量称为顶点vi的最大服务距离，记为e(vi )。 那么，中心点的布局问题是求出网络图g的中心点，求出中心点的布局问题的数学记述，例2 :某县部下的6个乡镇和之间的道路的连接如图所示。 各顶点表示乡镇，各边表示连接两个乡镇之间的道路，各边旁边的数字表示该道路的长度。 现在设立消防站，为全县六个乡镇服务。 该消防署应该设置哪个乡镇(顶点)，图10.2.2，解：第一步骤：用标签法求出从各顶点vi到其他各顶点vj的最短路径长度dij(i，j=1，2，6 )，将它们写入以下的距离矩阵，第二步骤：各顶点的最大服务显然，这些是矩阵d中每一行的最大值，且e(v1)=6，e(v2)=7，e(v3)=6，e(v4)=7，e(v5)=6，e(v6)=7。 步骤3 :判定。 因为e(v1)=e(v3)=e(v5)=mine(vi)=6，所以v1、v3、v5是中心点。 也就是说，消防署可以设置在v1、v3、v5的任何顶点。然后按一下。 中点选择问题的质量标准使从具有最佳选择位置的顶点到网络图中其他顶点的最短路径距离之和(或各顶点的加权总和)最小化。 (二)中位点的布局问题、中位点的布局问题的数学描述，G=(V，e )是没有简单连通的权利的图，连接两个顶点的边的权值是该两个顶点间的距离的各顶点VI (I=1，2，n )有正的负荷a(vi )，其他各顶点的最短路径长度为dii 那么，中点的选择问题是求图g的中点，例3 :某县的下位7个乡镇、各乡镇所有的人口a (VI ) (I=1，2，、7 )和各乡镇间的距离wij(i，j=1，