在matlab中求解最短路编程

ubeautqq

运筹学学完最短路问题心血来潮，想通过matalb编程实现一下。
; ~% L) r+ F6 v' m7 g# G9 R$ J- t# @1 a
& e  \& j- M& X& y. \! I) l算法步骤是课上学的，如下：
7 Z/ x& ]0 H; X% _/ q1.令起点标号为0，即b(s)=0,
$ m2 k* P0 K6 C) s9 x" g' j2.找出所有已标号vi和未标号vj的弧的集合，B={(i,j)},如果这样的弧不存在或者终点vt已标号，则计算结束
; W* s$ r6 H. g' Y% i3.计算集合B中弧k(i,j)=b(i)+d(i,j)的标号
4.选一个点标号，b(l)=min{k(i,j)|(i,j)属于B},在最小的k(i,j)的终点j处标号b(l),返回第二步。
例题如图：

% L2 H  X6 P4 r

数字代表最短路问题里的运费或者时间。
; e9 n: J* E, k& Q+ k9 Z4 x废话不多bb,纯手工代码如下hhhh:
; g6 ^! u' V$ k) }" G$ Wfunction [R,T] = minways( )
' n/ L3 I1 o" k%最短路问题
: [) u+ a, b6 M/ p5 N: ^D=[inf,8,6,2,inf,inf,inf;inf,inf,inf,inf,5,inf,inf;inf,5,inf,2,inf,4,inf;
    inf,inf,3,inf,inf,2,inf;inf,inf,inf,inf,inf,inf,5;
8 s% ?0 j  L4 |( `    inf,3,inf,inf,10,inf,7;inf,inf,inf,inf,inf,inf,inf];
R=[0,inf,inf,inf,inf,inf,inf];
& d$ L4 {8 |( UTotal=[1,2,3,4,5,6,7];
Done=[1];
Candidate=[2,3,4,5,6,7];
+ _. U% x7 C8 _9 ?- {: pR(1)=0;
while (R(7)>1000)
6 T" M" b- z7 J4 X1 g& \: ^* ya=length(Done);
b=length(Candidate);
t=1;
K={};
  a0 E9 T7 n/ H3 y8 zfor i=1:a
    for j=1:b
6 Z* x+ ~* F2 T& ~& F4 i  K{t}(i,j)=R(Done(i))+D(Done(i),Candidate(j));
: F) S2 E6 z' Q( w$ r+ A    end
end
2 m3 ~8 s+ v( M: e. W, Lif a==1
[biaohao,number]=min(K{t});
else
( @0 D" M4 L) K6 Fx0=min(K{t});
[biaohao,number]=min(x0);
* B1 o+ }# H/ H0 Z$ r9 eend
/ T: \! {. L% J9 zbeibiaohao=Candidate(number);
Done=[Done,beibiaohao];
Candidate(Candidate==beibiaohao)=[];
9 c  F6 M7 p, l9 ^) K! G1 rR(beibiaohao)=biaohao;
  ?/ G0 f8 U, ~, Y' n  Bt=t+1;
end
% U/ h$ I3 k, C: |. c# yT=R(7);
end
" Z" d* _# D4 ^, \+ \4 L: ?
写出来了很开心！！！
: l4 g- r2 Q& p+ e也发现了matalb的矩阵是多么的调皮，不听爸爸的话！

希望能给对这个问题感兴趣的提供一点微小的帮助。

yin123

在matlab中求解最短路编程