教案_图论31.ppt

《教案_图论31.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三节最短路问题一、最短路问题例下图为单行线交通网，每弧旁的数字表示通过这条线所需的费用。现在某人要从v1出发，通过这个交通网到v8去，求使总费用最小的旅行路线。v2v523464v3v1v4v6121061210v8v9v72363从v1到v8：P1=（v1，v2，v5，v8）费用6+1+6=13P2=（v1，v3，v4，v6，v7，v8）费用3+2+10+2+4=21P3=……从v1到v8的旅行路线从v1到v8的路。旅行路线总费用路上所有弧权之和。最短路问题中，不考虑有向环、并行弧。v2v523464v3v1v4v6121061210v8v9v72363最

2、短路问题给定有向网络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的最短路。最短路的子路也

3、是最短路。思想：将D=（V，A，W）中vs到所有其它顶点的最短路按其路长从小到大排列为：u0≤u1≤u2≤…≤unu0表示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的最短路长度的上界，相

4、应的点记“临时”标号，供进一步计算使用。前点标号i:表示点vs到vj的最短路上vj的前一点。如i=m，表示vs到vj的最短路上vj前一点是vm。1,6图上标号法:v5v223464v3v1v4121061210v8v9v72363v60,01,∞1,∞1,11,∞1,∞1,∞1,31,6图上标号法:v5v223464v3v1v4121061210v8v9v72363v60,01,∞1,∞1,11,∞1,∞1,∞1,31,6图上标号法:v5v223464v3v1v4121061210v8v9v72363v60,01,∞4,111,11,∞1,∞1,∞1,31

5、,5图上标号法:v5v223464v3v1v4121061210v8v9v72363v60,01,∞4,111,11,∞1,∞1,∞1,31,61,5图上标号法:v5v223464v3v1v4121061210v8v9v72363v60,01,∞4,111,11,∞1,∞1,∞1,33,53,5图上标号法:v5v223464v3v1v4121061210v8v9v72363v60,01,∞4,111,11,∞1,∞1,31,∞3,5图上标号法:v5v223464v3v1v4121061210v8v9v72363v60,01,∞4,111,11,∞1,∞1,31

6、,∞3,5图上标号法:v5v223464v3v1v4121061210v8v9v72363v60,04,111,11,∞2,61,∞1,31,∞3,5图上标号法:v5v223464v3v1v4121061210v8v9v72363v60,04,111,11,∞2,61,∞1,31,∞3,5图上标号法:v5v223464v3v1v4121061210v8v9v72363v60,05,101,11,∞2,65,121,35,93,5图上标号法:v5v223464v3v1v4121061210v8v9v72363v60,05,101,11,∞2,65,121,35,

7、9Dijkstra算法步骤：第1步：令us=0，uj=wsj（1≤j≤n）若asjA，则第2步：(选永久标号)在XK中选一点vi，满足第3步：（给点vi永久性标号）第4步：(修改临时标号)对所有如果令i=i，uj=ui+wij否则,i,,uj不变,把k换成k+1，返回第2步。如果ui=+，停止，令Xk+1=Xk∪﹛vi﹜,Xk+1=Xk＼﹛vi﹜令wsj=+,X0={vs},X0=VX0,k=0,i=0(0≤j≤n）从vs到XK中各点没有路；否则，转第3步。如果Xk+1=，结束，到所有的点的最短路已经求得；否则，转第4步。例用Dijkstra算

8、法求前面例子中从v1到各点的最短路。解