inf 0 inf 2;...РInf inf inf inf inf inf inf inf inf inf inf inf inf inf 0 1;...РInf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 0]Р n=size(w,1);Р w1=w(1,:);Р Р %赋初值Р for i=1:nР l(i)=w1(i);Р z(i)=1;Р endР s=[];Р s(1)=1;Р u=s(1);Р k=1Р lР zР Рwhile k<nР % 更新 l(v) 和 z(v)Р for i=1:nР for j=1:kР if i~=s(j) Р if l(i)>l(u)+w(u,i)Р l(i)=l(u)+w(u,i);Р z(i)=u;Р endР endР endР endР lР zР Р %求v*Р ll=l;Р for i=1:nР for j=1:kР if i~=s(j)Р ll(i)=ll(i);Р else Р ll(i)=inf;Р endР endР endР Р lv=inf;Р for i=1:nР if ll(i)<lvР lv=ll(i);Р v=i;Р endР end Р lvР vР Р s(k+1)=vР k=k+1Р u=s(k)Р РendРlРzР程序运行结果为:Р于是从A到B的最短路线为:A->C->F->J->M->O->B,其长度为16。Р三、参考文献:Р[1]钱颂迪,运筹学[M].北京:清华大学出版社,2002Р[2]谬慧芬,邵小兵,动态规划算法的原理及应用[J].中国科技信息,2005Р[3]蒋琦玮,陈P台亚物流配送最短径路的动态规划方法研究[J].系统工程,Р 2007Р[4]陈理能数学建模导论[M].北京:北京邮电大学出版社,1999
全文预览
