运筹学 最短路问题.ppt

* 第八章 最短路问题 第一节 最短路问题引例 例 下图为单行线交通网，每有向边旁的数字表示通过这 条线所需的费用。现在某人要从v1出发，通过这个交 通网到v8去，求使总费用最小的旅行路线。 v2 v5 2 3 4 6 4 v3 v1 v4 v6 1 2 10 6 1 2 10 v8 v9 v7 2 3 6 3 从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 3 6 3 最短路问题 给定有向网络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。 计算过程中可采用标号方法。 vs 到vi 的最短路长度已求出，相应的点记“永久”标号；vs 到vi 的最短路长度尚未求出,相应的点记“临时”标号。 前点标号?j: 表示点vs到vj的最短路上vj的前一点。 如?j=m，表示vs到vj的最短路上vj前一点是vm。 第二节 最短路的标号算法 当所有 wij ≥0 时，本算法是用来求给定点vs到任一个点vj 最短路的公认的最好方法。 事实：如果P是D中从vs到vj的最短路，vi是P中的一个点，那么，从vs沿P到vi的路是从vs到 vi的最短路。 最短路的子路也是最短路。 1,6 图上标号法: v5 v2 2 3 4 6 4 v3 v1 v4 1 2 10 6 1 2 10 v8 v9 v7 2 3 6 3 v6 0,0 1, ∞ 1, ∞ 1,1 1, ∞ 1, ∞ 1, ∞ 1,3 1,6 图上标号法: v5 v2 2 3 4 6 4 v3 v1 v4 1 2 10 6 1 2 10 v8 v9 v7 2 3 6 3 v6 0,0 1, ∞ 1, ∞ 1,1 1, ∞ 1, ∞ 1, ∞ 1,3 1,6 图上标号法: v5 v2 2 3 4 6 4 v3 v1 v4 1 2 10 6 1 2 10 v8 v9 v7 2 3 6 3 v6 0,0 1, ∞ 4,11 1,1 1, ∞ 1, ∞ 1, ∞ 1,3 1,5 图上标号法: v5 v2 2 3 4 6 4 v3 v1 v4 1 2 10 6 1 2 10 v8 v9 v7 2 3 6 3 v6 0,0 1, ∞ 4,11 1,1 1, ∞ 1, ∞ 1, ∞ 1,3 1,6 3,5 图上标号法: v5 v2 2 3 4 6 4 v3 v1 v4 1 2 10 6 1 2 10 v8 v9 v7 2 3 6 3 v6 0,0 1, ∞ 4,11 1,1 1, ∞ 1, ∞ 1,3 1, ∞ 3,5 图上标号法: v5 v2 2 3 4 6 4 v3 v1 v4 1 2 10 6 1 2 10 v8 v9 v7 2 3 6 3 v6 0,0 4,11 1,1 1, ∞ 2,6 1, ∞ 1,3 1,∞