最短路径与选址问题1.ppt

第二节 最短路径与选址问题 一、最短路径问题 （1）“纯距离”意义上的最短路径。 例如，需要运送一批物资从一个城市到另一个城市，选择什么样的运输路线距离最短？ （2）“经济距离”意义上的最短路径。 例如，某公司在10大港口C1，C2，…，C10设有货栈，从Ci到Cj之间的直接航运价格，是由市场动态决定的。如果两个港口之间无直接通航路线，则通过第三个港口转运。那么，各个港口之间最廉价的货运线路是什么？ （3）“时间”意义上的最短路径。 例如，某家经营公司有一批货物急需从一个城市运往另一个城市，那么，在由公路、铁路、河流航运、航空运输等四种运输方式和各个运输线路所构成的交通网络中，究竟选择怎样的运输路线最节省时间？ （二）最短路径的算法 最短路径问题最好的求解方法：1959年，E．W．Dijkstar 提出的标号法。 标号法优点 不仅可以求出起点到终点的最短路径及其长度，而且可以求出起点到其它任何一个顶点的最短路径及其长度； 同时适用于求解有向图或无向图上的最短路径问题。 ▇ 标号法具体计算步骤 ① 如果刚刚得到P标号的点是vi，那么，对于所有这样的点 将其T标号修改为：min[T(vj)，P(vi)+wij]。 ② 若G中没有T标号，则停止。否则，把点 的T标号修改为P标号，然后再转入①。其中， 满足： 二、选址问题 选址问题，是现代地理学的分支学科——区位论 研究的主要方向之一。选址问题涉及人类生产、生活、文化、娱乐等各个方面。 选址问题的数学模型取决于两个方面的条件 ：①可供选址的范围、条件；②怎样判定选址的质量。 本节的讨论仅限于选址的范围 是一个地理网络，而且选址位置 位于网络图的某一个或几个顶点上。 对这样的选址问题，根据其选址的质量判据，可以将其归纳为求网络图的中心点与中位点 两类问题。 （一）中心点选址问题 （二）中位点选址问题 中位点选址问题的质量判据： 使最佳选址位置所在的顶点到网络图中其它各个顶点的最短路径距离的总和（或者以各个顶点的载荷加权求和）达到最小。 中位点选址问题的数学描述:  设G＝（V，E）是一个简单连通赋权无向图，连接两个顶点的边的权值为该两顶点之间的距离；对于每一个顶点vi（i＝1，2，…，n），有一个正的负荷a(vi)，而且它与其它各顶点之间的最短路径长度为di1，di2，…，din。那么，中位点选址问题，就是求图G的中位点 ，使得： * * 对于许多地理问题，当它们被抽象为图论意义下的网络图时，问题的核心就变成了网络图上的优化计算问题。其中，最为常见的是关于路径和顶点的优选计算问题。 在路径的优选计算问题中，最常见的是最短路径问题；而在顶点的优选计算问题中，最为常见的是中心点和中位点选址问题。 （一）最短路径的含义 ◣以上三类问题，都可以抽象为同一类问题，即赋权图上的最短路径问题。◣不同意义下的距离都可以被抽象为网络图中边的权值。 ◣权——这种权值既可以代表“纯距离 ”，又可以代表“经济距离 ”，也可以代表“时间距离 ”。 标号法的基本思想 设是一个赋权有向图，即对于图中的每一条边，都赋予了一个权值。在图G中指定两个顶点，确定为起点和终点，不妨设为起点，为终点。 标号法的基本思想是： 首先v1从开始，给每一个顶点标一个数，称为标号。这些标号，又进一步区分为T标号和P标号两种类型。其中，每一个顶点的T标号表示从起点v1到该点的最短路径长度的上界，这种标号为临时标号；P标号表示从v1到该点的最短路长度，这种标号为固定标号。 在最短路径计算过程中，对于已经得到P标号的顶点，不再改变其标号；对于凡是没有标上P标号的顶点，先给它一个T标号；算法的每一步就是把顶点的T标号逐步修改，将其变为P标号。 那么，最多经过k-1步，就可以求得到从起点v1到每一个顶点的最短路径及其长度。 开始，先给v1标上P标号P(v1)＝ 0，其余各点标上T标号T(vj)＝+∞（j≠1）。 例1：在图10.2.1所示的赋权有向图中，每一个顶点vi（i=1，2，…，n）代表一个城镇；每一条边代表相应两个城镇之间的交通线，其长度用边旁的数字表示。试求城镇v1到v7之间的最短路径。 图10.2.1 赋权有向交通网络图 解： 首先给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标号，所