资源描述：
《数学建模迪杰斯特拉算法例题.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数学建模专题练习迪杰斯特拉算法2014.09例一、用Dijkstra算法求下图从v1到v6的最短路。v1v2v3v4v6v5352242421解（1）首先给v1以P标号，给其余所有点T标号。（2）v1v2v3v4v6v5352242421（4）v1v2v3v4v6v5352242421（5）（6）反向追踪得v1到v6的最短路为：237184566134105275934682例二.求从1到8的最短路径237184566134105275934682X={1}min{d12,d14,d16}=min{0+2,0+1,0+3}=min{2,1,3}=1X={1,
2、4},p4=1p4=1p1=0237184566134105275934682X={1,4}min{d12,d16,d42,d47}=min{0+2,0+3,1+10,1+2}=min{2,3,11,3}=2X={1,2,4},p2=2p1=0p4=1p2=2237184566134105275934682X={1,2,4}min{d16,d23,d25,d47}=min{0+3,2+6,2+5,1+2}=min{3,8,7,3}=3X={1,2,4,6},p6=3p2=2p4=1p1=0p6=3237184566134105275934682X={1,2,
3、4,6}min{d23,d25,c47,d67}=min{2+6,2+5,1+2,3+4}=min{8,7,3,7}=3X={1,2,4,6,7},p7=3p2=2p4=1p1=0p6=3p7=3237184566134105275934682X={1,2,4,6,7}min{d23,d25,d75,d78}=min{2+6,2+5,3+3,3+8}=min{8,7,6,11}=6X={1,2,4,5,6,7},p5=6p2=2p4=1p1=0p6=3p7=3p5=6237184566134105275934682X={1,2,4,6,7}min{d23,d
4、53,d58,d78}=min{2+6,6+9,6+4,3+8}=min{8,15,10,11}=8X={1,2,3,4,5,6,7},p3=8p2=2p4=1p1=0p6=3p7=3p5=6p3=8237184566134105275934682X={1,2,3,4,6,7}min{d38,d58,d78}=min{8+6,6+4,3+7}=min{14,10,11}=10X={1,2,3,4,5,6,7,8},p8=10p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10237184566134105275934682X={1,2,3,4,
5、6,7,8}1到8的最短路径为{1，4，7，5，8}，长度为10。p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10例三.下图为单行线交通网，每弧旁的数字表示通过这条线所需的费用。现在某人要从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的路。旅行路线总费用路上所有弧权之和。最
6、短路问题中，不考虑有向环、并行弧。v2v523464v3v1v4v6121061210v8v9v72363最短路问题给定有向网络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。当所有wij≥0时，本算法是用来求给定点vs到任一个点vj最短路的公认的最好方法。事实：如果P是D中从vs到vj的最短路
7、，vi是P中的一个点，那么，从vs沿P到vi的路是从vs到vi的最短路。最短路的子路也是最短路。思想：将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的
8、最短路长度，相应的点记“永久”标号；XK中的点，ui
