北京交通大学经济管理学院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的最短路。 最短路的子路也是最短路