文档介绍：最短路径与选址问题
最短路径问题
选址问题
来自大的资料库下载
对于许多地理问题,当它们被抽象为图论意义下的网络图时,问题的核心就变成了网络图上的优化计算问题。其中,最为常见的是关于路径和顶点的优选计算问题。
在路径的优选计算问题中,最常见的是最短路径问题;而在顶点的优选计算问题中,最为常见的是中心点和中位点选址问题。
来自大的资料库下载
“纯距离”意义上的最短路径
例如,需要运送一批物资从一个城市到另一个城市,选择什么样的运输路线距离最短?
“经济距离”意义上的最短路径 例如,某公司在10大港口C1,C2,…,C10设有货栈,从Ci到Cj之间的直接航运价格,是由市场动态决定的。如果两个港口之间无直接通航路线,则通过第三个港口转运。那么,各个港口之间最廉价的货运线路是什么?
一、最短路径问题
(一)最短路径的含义
“时间”意义上的最短路径 例如,某家经营公司有一批货物急需从一个城市运往另一个城市,那么,在由公路、铁路、河流航运、航空运输等4种运输方式和各个运输线路所构成的交通网络中,究竟选择怎样的运输路线最节省时间?
以上3类问题,都可以抽象为同一类问题,即赋权图上的最短路径问题。 不同意义下的距离都可以被抽象为网络图中边的权值。
权——这种权值既可以代表“纯距离”,又可以代表“经济距离”,也可以代表“时间距离”。
(二)最短路径的算法
标号法
提出的标号法是最短路径问题最好的求解方法。
标号法优点 不仅可以求出起点到终点的最短路径及其长度,而且可以求出起点到其他任何一个顶点的最短路径及其长度;同时适用于求解有向图或无向图上的最短路径问题。.
来自大的资料库下载
标号法的基本思想
设G是一个赋权有向图,即对于图中的每一条边,都赋予了一个权值。在图G中指定两个顶点,确定为起点和终点,不妨设v1为起点,vk为终点。
首先从v1开始,给每一个顶点标一个数,称为标号。这些标号,又进一步区分为T标号和P标号两种类型。其中,每一个顶点的T标号表示从起点v1到该点的最短路径长度的上界,这种标号为临时标号;P标号表示从v1到该点的最短路长度,这种标号为固定标号。
在最短路径计算过程中,对于已经得到P标号的顶点,不再改变其标号;对于凡是没有标上P标号的顶点,先给它一个T标号;算法的每一步就是把顶点的T标号逐步修改,将其变为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)代表一个城镇;每一条边代表相应两个城镇之间的交通线,其长度用边旁的数字表示。试求城镇v1到v7之间的最短路径。
赋权有向交通网络图
解:首先给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+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。