物流信息管理
大连海事大学
第五章 地理信息系统
最短路径原理与算法
1. 数学模型 2. 标号法 3. 程序流程
最短路径问题
（一）最短路径的含义
二、最短路径问题
（一）最短路径的含义
“纯距离”意义上的最短路径
例如，需要运送一批物资从一个城市到另 一个城市，选择什么样的运输路线距离最短？
“经济距离”意义上的最短路径
标号法例子
标号法例子
最小生成树
v y
节点
u v
前溯节点
u u u v w w x yxBiblioteka uzw y x
t w s
s t z
marked(N) = false stpdis(N) = OO preid(N) = -1
‘标记数组 ‘最短距离 ‘前溯节点号
startid
crtid
endid
tmpid crtid = startid ‘设置当前节点 while crtid <> endid ‘搜索直到终点 for linkid = 1 to L ‘搜索所有链接 if link.o = crtid then ‘如果与当前节点邻接 tmpid = link.d ‘并且另一端点的最短距离较大 if stpdis(crtid) + link.dis < stpdis(tmpid) then stpdis(tmpid) = stpdis(crtid) + link.dis preid(tmpid) = crtid ‘修改另一端点的最短距离和前溯节点 end if end if next
标号法具体计算步骤
开始，先给v1标上P标号P(v1)＝ 0，其余各点 标上T标号T(vj)＝+∞（j≠1）。 ① 如果刚刚得到P标号的点是vi，那么，对于 所有这样的点 v j vi , v j E , 而且 v j的标号是 T标号 将其T标号修改为：min[T(vj)，P(vi)+wij]。 v j0 ② 若G中没有T标号，则停止。否则，把点 的T标号修改为P标号，然后再转入①。 v j0 满足 T (v j0 ) minT (v j ) 其中，
