空间分布的测度.ppt

《空间分布的测度.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、2.最短路径shortestpath对于许多地理问题，当它们被抽象为图论意义下的网络图时，问题的核心就变成了网络图上的优化计算问题。其中，最为常见的是关于路径和顶点的优选计算问题。在路径的优选计算问题中，最常见的是最短路径问题；而在顶点的优选计算问题中，最为常见的是中心点和中位点选址问题。最短路径的算法标号法1959年E.W.Dijkstar提出的标号法是最短路径问题最好的求解方法。标号法优点不仅可以求出起点到终点的最短路径及其长度，而且可以求出起点到其他任何一个顶点的最短路径及其长度；同时适用于求解有向图或无向图上的最短路径

2、问题。标号法的基本思想设G是一个赋权有向图，即对于图中的每一条边，都赋予了一个权值。在图G中指定两个顶点，确定为起点和终点，不妨设v1为起点，vk为终点。首先从v1开始，给每一个顶点标一个数，称为标号。这些标号，又进一步区分为T标号和P标号两种类型。其中，每一个顶点的T标号表示从起点v1到该点的最短路径长度的上界，这种标号为临时标号；P标号表示从v1到该点的最短路长度，这种标号为固定标号。在最短路径计算过程中，对于已经得到P标号的顶点，不再改变其标号；对于凡是没有标上P标号的顶点，先给它一个T标号；算法的每一步就是把顶点的T标

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

4、度用边旁的数字表示。试求城镇v1到v7之间的最短路径。有向图及其长度V1V2V4V3V5V7V62233559691174解：首先给v1标上P标号P(v1)=0，表示从v1到v1的最短路径为零。其他点(v2，v3，…，v7)标上T标号T(vj)＝+∞（j＝2，3，…，7）。第1步：①v1是刚得到P标号的点。因为(v1，v2)，(v1，v3)，(v1，v4)∈E，而且v2，v3，v4是T标号，所以修改这3个点的T标号为T(v2)＝min[T(v2)，P(v1)+w12]＝min[+∞，0+9]＝9T(v3)＝min[T(v3)，

5、P(v1)+w13]＝min[+∞，0+7]＝7T(v4)＝min[T(v4)，P(v1)+w14]＝min[+∞，0+2]＝2②在所有T标号中，T(V4)＝2最小，于是令P(V4)＝2。第2步：①v4是刚得到P标号的点。因为(v4，v3)，(v4，v6)∈E，而且v3，v6是T标号，故修改v3，v6的T标号为T(v3)＝min[T(v3)，P(v4)+w43]＝min[7，2+4]＝6T(v6)＝min[T(v6)，P(v4)+w46]＝min[+∞，2+3]＝5②在所有的T标号中，T(v6)＝5最小，故令P(v6)＝5。第

6、2步：①v6是刚得到P标号的点。因为(v6，v2)，(v6，v5)，(v6，v7)∈E，而且v2,v5，v7是T标号，故修改v2,v5，v7的T标号为T(v2)＝min[T(v2)，P(v6)+w62]＝min[9，5+3]＝8T(v5)＝min[T(v5)，P(v6)+w65]＝min[+∞，5+11]＝16T(v7)＝min[T(v7)，P(v6)+w67]＝min[+∞，5+9]＝14②在所有的T标号中，T(v3)＝6最小，于是令P(v3)＝6。第4步：①v3是刚得到P标号的点。因为(v3，v2)，(v3，v4)∈E，而

7、且v2为T标号，故修改v2的T标号为T(v2)＝min[T(v2)，P(v3)+w32]＝min[8，6+5]＝8②在所有的T标号中，T(v2)＝8最小，故令P(v2)＝8。第5步：①v2是刚得到P标号的点。因为(v2，v5)∈E，而且v5是T标号，故修改它们的T标号为T(v5)＝min[T(v5)，P(v2)+w25]＝min[16，8+5]=13②在所有T标号中，T(v5)＝13最小，于是令：P(v5)＝13。第6步：①v5是刚得到P标号的点。因为(v5，v7)∈E，而且v7为T标号，故修改它的T标号为T(v7)＝min[

8、T(v7)，P(v5)+w57]＝min[14，13+6]=14②目前只有v7是T标号，故令：P(v7)＝14。从v1到v7之间的最短路径为(v1，v4，v6，v7)，最短路径长度为14。3.服务点的最优区位问题选址问题，是现代地理学研究的主要问题之一。选址问题涉及人类生产、