动态规划求最短路径的两种方法

1、动态规划1最短路线问题3解（1）：将上图该画成下图：3记a（1,2）=4，a(1,3=5，依次类推，表示每个点和值的关系。逆序递推方程：如图各状态：状态6逆序递推，找出上一个状态到下一阶段的最小路径值。例如，当K=4时，状态 它们到F 点需经过中途点E，需一一分析从E 到 F的最短路：先说从D1到F 的最短路有两种选择：经过 E1, E2, 比较最短。这说明由 D1 到F 的最短距离为7，其路径为a=0,4,5,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf4,0,inf,2,3,6,inf,inf,inf,inf,inf,inf,inf5,inf,0,inf,

2、8,7,7,inf,inf,inf,inf,inf,infinf,2,inf,0,inf,inf,inf,5,8,inf,inf,inf,infinf,3,8,inf,0,inf,inf,4,5,inf,inf,inf,infinf,6,7,inf,inf,0,inf,inf,3,4,inf,inf,infinf,inf,7,inf,inf,inf,0,inf,8,4,inf,inf,infinf,inf,5,4,inf,inf,inf,0,inf,inf,3,5,infinf,inf,inf,8,5,3,8,inf,0,inf,6,2,infinf,inf,inf,inf,inf,4,4,i

3、nf,inf,0,1,3,infinf,inf,inf,inf,inf,inf,inf,3,6,1,0,inf,4inf,inf,inf,inf,inf,inf,inf,5,2,3,inf,0,3inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,4,3,0;s8=min(a(8,11+a(11,13,a(8,12+a(12,13;s9=min(a(9,11+a(11,13,a(9,12+a(12,13;s10=min(a(10,11+a(11,13,a(10,12+a(12,13;s4=min(a(4,8+s8,a(4,9+s9;s5=min(a(5,8+s8,a

4、(5,9+s9;s6=min(a(6,9+s9,a(6,10+s10;s7=min(a(7,9+s9,a(7,10+s10;s2=a(2,4+s4,a(2,5+s5,a(2,6+s6;s2=min(s2;s3=a(3,5+s5,a(3,6+s6,a(3,7+s7;s3=min(s3;s1=min(a(1,2+s2,a(1,3+s3运行结果为：s8 = 7 s9 = 5 s10 = 5 s4 = 12 s5 = 10 s6 = 8 s7 = 9 s2 =13s3 = 15 s1 = 17结果分析：s表示每个点到终点的最短距离，那么最短路程为17。依据数据从图中可推出最短路径为：解（2）：运用Fl

5、oyd算法求取动态规划中最短距离及路线。MATLAB程序：a=0,4,5,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf4,0,inf,2,3,6,inf,inf,inf,inf,inf,inf,inf5,inf,0,inf,8,7,7,inf,inf,inf,inf,inf,infinf,2,inf,0,inf,inf,inf,5,8,inf,inf,inf,infinf,3,8,inf,0,inf,inf,4,5,inf,inf,inf,infinf,6,7,inf,inf,0,inf,inf,3,4,inf,inf,infinf,inf,7,inf,inf

6、,inf,0,inf,8,4,inf,inf,infinf,inf,5,4,inf,inf,inf,0,inf,inf,3,5,infinf,inf,inf,8,5,3,8,inf,0,inf,6,2,infinf,inf,inf,inf,inf,4,4,inf,inf,0,1,3,infinf,inf,inf,inf,inf,inf,inf,3,6,1,0,inf,4inf,inf,inf,inf,inf,inf,inf,5,2,3,inf,0,3inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,4,3,0;n=size(a,1;D=a;path=zeros(n,n;for i=1:nfor j=1:nif D(i,j=infpath(i,j=j;end;end;end;for k=1:nfor i=1:nfor j=1:nif D(i,k+D(k,j D(i,j=D(i,k+D(k,j;path(i,j=path(i,k;end;end;end;end;D(1,13w1=path(1,13;w2=path(w1,13;w3=path(w2,13;w4=path(w3,