第五章地理信息系统-路径遍历与最短路径概述.pptx

物流信息管理;第五章 地理信息系统;路径遍历与最短路径;一、路径遍历;1.深度优先遍历;Sub DeepthFirstSearch(v as Integer) ‘从v出发深度优先遍历图g Call visit(v) visited(v) = 1 w=FIRSTADJ(v) ‘w为v的邻接点 Do while visited(w)=0 ‘当邻接点未访问 Call DeepthFirstSearch(w) w=NEXTADJ(v) ‘找下一邻接点 Loop End Sub;2.广度优先遍历;Call visit(s) visited(s) = 1 Sub BreadthFirstSearch(v as Integer) ‘从v出发广度优先遍历图g For i=1 to NUMOFADJ(v) w(i) = NEXTADJ(v) ‘找下一邻接点 If visited( w(i) ) = 0 Then Call visit( w(i) ) visited( w(i) ) = 1 End If Next For j=1 to NUMOFITEMS(w) Call BreadthFirstSearch( w(j) ) Next End Sub;二、最短路径问题;“纯距离”意义上的最短路径 例如，需要运送一批物资从一个城市到另一个城市，选择什么样的运输路线距离最短？ “经济距离”意义上的最短路径 例如，某公司在10大港口C1，C2，…，C10设有货栈，从Ci到Cj之间的直接航运价格，是由市场动态决定的。如果两个港口之间无直接通航路线，则通过第三个港口转运。那么，各个港口之间最廉价的货运线路是什么？; “时间”意义上的最短路径 例如，某家经营公司有一批货物急需从一个城市运往另一个城市，那么，在由公路、铁路、河流航运、航空运输等4种运输方式和各个运输线路所构成的交通网络中，究竟选择怎样的运输路线最节省时间？ ;（二）最短路径的算法;标号法的基本思想 设G是一个赋权有向图，即对于图中的每一条边，都赋予了一个权值。在图G中指定两个顶点，确定为起点和终点，不妨设v1为起点，vk为终点。 首先从v1开始，给每一个顶点标一个数，称为标 号。这些标号，又进一步区分为T标号和P标号两种类型。其中，每一个顶点的T标号表示从起点v1到该点的最短路径长度的上界，这种标号为临时标号；P标号表示从v1到该点的最短路长度，这种标号为固定标号。 在最短路径计算过程中，对于已经得到P标号的顶点，不再改变其标号；对于凡是没有标上P标号的顶点，先给它一个T标号；算法的每一步就是把顶点的T标号逐步修改，将其变为P标??。 那么，最多经过k-1步，就可以求得到从起点v1到每一个顶点的最短路径及其长度。 ;标号法具体计算步骤 ;15;标号法例子;标号法例子;最短路径生成树