smin.m

Matlab源程序用动态规划方法求最短路径。

%clear;
%BH=[1,3,2,2,1];
%s(1,1:BH(2),1:BH(1))=[6;3;3];
%s(2,1:BH(3),1:BH(2))=[6,8,7;5,6,4];
%s(3,1:BH(4),1:BH(3))=[6,8;7,9];
%s(4,1:BH(5),1:BH(4))=[5,6];
function [dmin,NUM,D]=smin(BH,s)
temp=size(BH);
l=temp(2);
mnp=ones(1,max(BH)).*inf;
mn(1:BH(1))=0;
for L=2:l;
    for H2=1:BH(L)
        for H1=1:BH(L-1)
            mnp(H1)=s(L-1,H2,H1)+mn(L-1,H1);
        end
        [mn(L,H2),nummin(L-1,H2)]=min(mnp);
        mnp=ones(1,max(BH)).*inf;
    end
end
[dmin,nummin(L,1)]=min(mn(l,1:BH(l)));

NO(1)=nummin(l,1);
for L=2:l
NO(L)=nummin(l+1-L,NO(L-1));
end
NUM=rot90(rot90(NO));
for L=1:l-1
    D(L)=s(L,NUM(L+1),NUM(L));
end
D;
NUM;
dmin;