建模培训课程2-最短路问题.docx

最短路径问题 一）手算 红框表示当前之前已经选取的最短路径上的顶点紫色表示当前所要选取的最短路径的顶点 绿色表示当前还未选取为最短路径上的点 注：这里最短路的 Dijkstra 算法中一定要注意每计算一个 l(v)时，应该是在前一个已标号的顶点 ui 的相邻点中取最小值 min(l(v),l(ui)+w(ui,v))得到的。 二）数学软件计算 例 如下图，求 v1 到其它各点最短距离 Matlab 解法 Dijkstra 算法求最短路 注意到程序中语句：a=a+a;所以数据部分只需上三角数据。 clc,clear a=zeros(5); a(1,2)=10;a(1,5)=2; a(2,3)=5;a(2,4)=6;a(2,5)=7; a(3,4)=4; a(4,5)=3; a=a+a; a(find(a==0))=inf; pb(1:length(a))=0;pb(1)=1;index1=1;index2=ones(1,length(a)); d(1:length(a))=inf;d(1)=0;temp=1; while sum(pb)length(a) tb=find(pb==0); d(tb)=min(d(tb),d(temp)+a(temp,tb)); tmpb=find(d(tb)==min(d(tb))); temp=tb(tmpb(1)); pb(temp)=1; index1=[index1,temp]; temp2=find(d(index1)==d(temp)-a(temp,index1)); index2(temp)=index1(temp2(1)); end d, index1, index2 结果显示： d = 0 9 9 5 2 index1 = 1 5 4 2 3 index2 = 1 5 4 5 1 解释：以下用 c(i)表示顶点 vi 1）d(i)表示 c(1)到 c(i)城市间最便宜路线的票价2）index1(i)=k 表示第 i 个获得标号的顶点是 c(k) index1(2)=5 表示第二个获得标号的顶点是 c(5)，index1(3)=4，说明第三个获得标号的顶点是 c(4)，等等 index2(2)=5 表示从 c(1)到 c(2)的最短路中，在到达 c(2)前的一个城市为 c(5)， 这时我们再可以查看 c(1)到 c(5)最短路中，到达 c(5)前的一个城市是多少，由index2(5)=1 知 c(5) 前一个城市为 c(1) ， 综上， 从 c(1)到 c(2) 最短路为： c(1)-c(5)-c(2) ， 对应 票价为 d(2)=9, 这点可以从矩阵 a 中得到验证， a(1,5)+a(5,2)=2+7=9 注意：由于每一次标号顶点对应的最短路上前一个顶点都由 index2 给出，则一定可以把整个最短路路线标出。 其余几个语句的相关解释 tb=find(pb==0); %存放未标号的的顶点d(tb)=min(d(tb),d(temp)+a(temp,tb)); %计算当前未标记的顶点距离 tmpb=find(d(tb)==min(d(tb))); %获取当前最短路上的该顶点在距离矩阵 d(tb)中的索引（即位 置），这个索引值也正好是 tb 矩阵中的该顶点索引 temp=tb(tmpb(1)); %tmpb 可能有多个索引，取第一个索引在 tb 矩阵中对应的元素，这个元素就 是当前获得最短路上的顶点。例如如果 temp=6，表示顶点 c6 pb(temp)=1; %对当前获得最短路顶点进行标记，以防止后面再对它考虑 Lingo 解法： Lingo 采用的解法是动态规划法，这里我们首先要了解一下动态规划的方法，请参考文献，此处略！ 为讨论问题方便，先看三个点的情况，设 F(i)表示顶点 vi 到 v3 的最短距离值， Dij 表示 vi 与 vj 之间边长，假如图 G 为： 求各顶点到v3的最短路径及距离？ 分析：易知，记F(3)=F_3=0 ，对于任意i3，F(i)=F(j)+D(i,j),此时如果等号取到，可以记P(i,j)=P_i_j=1，以表示最短路径中的一条边P(i,j)。用 lingo软件可以完全显示的表示如下： MODEL: TITLE 动态规划法寻找最短路; [_2] - D_1_2 + F_1 - F_2 = 0 ; [_3] - D_2_3 + F_2 = 0 ; [_4] P_1_2 = @IF( F_1 #EQ# D_1_2 + F_2 , 1 , 0 ) ; [_5] P_2_3 = @IF( F_2 #EQ# D_2_3 + 0 , 1 , 0 ) ; END 如果是如下情况，则同一个 i，i3 时 F(i)=F(j)+D(i,j) 有可能因 j 的