教案_图论31.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。 二、Dijkstra算法 当所有 wij ≥0 时，本算法是用来求给定点vs到任一个点vj 最短路的公认的最好方法。 事实：如果P是D中从vs到vj的最短路，vi是P中的一个点，那么，从vs沿P到vi的路是从vs到 vi的最短路。 最短路的子路也是最短路。 思想：将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’ 可取为vk+1。 计算过程中可采用标号方法。 Xk中的点，ui 值是vs 到vi 的最短路长度，相应的点记“永久”标号； XK中的点，ui值是vs到vi的最短路长度的上界，相应的点记“临时”标号，供进一步计算使用。 前点标号?i : 表示点vs到vj的最短路上vj的前一点。 如?i=m，表示vs到vj的最短路上vj前一点是vm。 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 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 3,5 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