北京交通大学经济管理学院nics and ManagomentSchool of EcononBaijing Jiaotong University图与网络分析第三节最短路问题
图与网络分析 第三节 最短路问题
北京第三节最短路问题一、最短路问题例下图为单行线交通网，每弧旁的数字表示通过这条线所需的费用。现在某人要从"出发，通过这个交通网到v去，求使总费用最小的旅行路线。VV229636233Z23420104210V72VV北京交通大学1
第三节 最短路问题 一、最短路问题 例 下图为单行线交通网，每弧旁的数字表示通过这条 线所需的费用。现在某人要从v1出发，通过这个交 通网到v8去，求使总费用最小的旅行路线。 v2 v5 2 3 4 6 4 v3 v1 v4 v6 1 2 10 6 1 2 10 v8 v9 v7 2 6 3 3
VV5212V963623322342%104210V72V4V6从y,到vg:费用 6+1+6=13Pi= (v1, V2, Vs, V8)费用3+2+10+2+4=21P2= (vi, V3, V4, Ve， V7, Vg)P3=从到v的旅行路线从到v的路。最短路问题中，不考虑有向环、并行弧。旅行路线总费用路上所有弧权之和
从v1到v8： P1 =（v1，v2，v5，v8） 费用 6+1+6=13 P2 =（v1，v3，v4， v6， v7， v8） 费用 3+2+10+2+4=21 P3= . 从v1到v8的旅行路线 从v1到v8的路。 旅行路线总费用 路上所有弧权之和。 最短路问题中，不考虑有向环、并行弧。 v2 v5 2 3 4 6 4 v3 v1 v4 v6 1 2 10 6 1 2 10 v8 v9 v7 2 6 3 3
最短路问题给定有向网络D=（V，A，W），任意弧a;EA，有权w（aj）=wij，给定D中的两个顶点v，V。设P是D中从v到v的一条路，定义路P的权（长度）是P中所有弧的权之和，记为w（P）。最短路问题就是要在所有从v到v的路中，求一条路P。，使w(P.) = min w(P)P称P是从到v的最短路。路P.的权称为从到v的路长。记为ust°
最短路问题 给定有向网络D=（V，A，W），任意弧aij∈A， 有权w（ aij ）=wij，给定D中的两个顶点vs，vt。设P 是D中从vs到vt的一条路，定义路P的权（长度）是P中 所有弧的权之和，记为w（P）。最短路问题就是要在 所有从vs到vt的路中，求一条路P0 ，使 称P0是从vs到vt的最短路。路P0的权称为从vs到vt 的路长。记为ust
北京交通大学经济管理学院二、Dijkstra算法School of EoiosandManagomenBojing Jiaotong University当所有wi≥0 时，本算法是用来求给定点>,到任一个点v;最短路的公认的最好方法。事实：如果P是D中从>到v的最短路，v;是P中的一个点，那么，从v沿P到v的路是从v到v的最短路。最短路的子路也是最短路。北京交通大学
二、Dijkstra算法 当所有 wij ≥0 时，本算法是用来求给定点vs到 任一个点vj 最短路的公认的最好方法。 事实：如果P是D中从vs到vj的最短路，vi是P中的一 个点，那么，从vs沿P到vi的路是从vs到 vi的最短路。 最短路的子路也是最短路
思想：将D=（V，A，W）中v到所有其它顶点的最短路按其路长从小到大排列为：uo≤uj≤uz ≤...≤u,u,表示>到自身的长度，相应最短路记为：Po，P，P2，.….，Pn，P,一定只有一条弧。记X=，Xo=V\Xo，则ur = min wsiv,i Xo取最小值的点为V,:P,-P(vs，V)假定 uo，u，，u的值已求出，对应的最短路分别为 Pi-P(vs,Vi), P2=P(vs,V2), ..., Pk=P(vs,Vk)
思想：将D=（V，A，W）中vs到所有其它顶点的最短 路按其路长从小到大排列为： u0≤ u1 ≤ u2 ≤.≤ un u0表示vs到自身的长度，相应最短路记为： P0，P1，P2，.，Pn， 取最小值的点为v1 , ∴P1=P(vs , v1 ) 假定 u0，u1，.，uk的值已求出，对应的最短路分别 为 P1=P(vs ,v1 ), P2=P(vs ,v2 ), ., Pk=P(vs ,vk ) P1一定只有一条弧
记V, Xh=VIXX, = ,, Vi,V2...Vmin (u, + w(v,,v'))则Uk+1v,1 XkviXk使上式达到最小值的点可取为Vk+1°计算过程中可采用标号方法X中的点，u;值是V,到v,的最短路长度，相应的点记“永久”标号；PermanentX中的点，u,值是v,到v,的最短路长度的上界，相应的点记“临时"标号，供进一步计算使用。Temporary前点标号贝表示点v到v,的最短路上v;的前一点。如m，表示v,到v;的最短路上y,前一点是vm
记 则 使上式达到最小值的点v ’ 可取为vk+1。 计算过程中可采用标号方法。 Xk中的点，ui 值是vs 到vi 的最短路长度，相 应的点记“永久”标号； XK中的点，ui值是vs到vi的最短路长度的上界， 相应的点记“临时”标号，供进一步计算使用。 前点标号i : 表示点vs到vj的最短路上vj的前一点。 如i =m，表示vs到vj的最短路上vj前一点是vm。 Temporary Permanent
北京交通大学经济管理学院schng.stEcongounomics and Managomentrsin[3, v2][9, v.][5, v, ]V(4, vs)(10,v4) V-(0, VN4VSV4,v][0,v,]V6[9, vg][7, vs[8, vs]22Vs[4, v2]V[1, v,]8北京交通大学
北京交通大学经济管理学院图论第七章StingsEonguntnics and Managoment[3, V2]V.V-[9,va](6, r V4(4, v)[9, V.][4,V3][9, vg]VSV[7, v,]26V313, v2 17,vs[0, v,][9, vg][1, v, ]22[8, vs][4,v2] V5[4, v]北京交通大学
第七章 图论
北京交通大学图上标号法：经济管理学院SchoalsIofEcononnics and ManagomentJiaotong University1,001,6122186362N1,333V1.8V3?4N0100,042110V12VVV61, 81,81,1北京交通大学
1,6 图上标号法 : v v 5 2 2 3 4 6 4 v 3 v 1 v 4 1 2 10 6 1 2 10 v 8 v 9 v 7 2 6 3 3 v 6 0,0 1, ∞ 1,1 1, ∞ 1, ∞ 1, ∞ 1, ∞ 1,3