在matlab中求解最短路编程

ubeautqq

* [: y7 k* y4 [% R; L4 ^% A; ^运筹学学完最短路问题心血来潮，想通过matalb编程实现一下。
2 F9 N# ]2 C6 V$ h3 ]
/ D- U" ]% v! a算法步骤是课上学的，如下：
1.令起点标号为0，即b(s)=0,
, ?& b- U( l& |0 ]. Z# Y2.找出所有已标号vi和未标号vj的弧的集合，B={(i,j)},如果这样的弧不存在或者终点vt已标号，则计算结束
+ |9 B" x' Q* j3 V" ]3.计算集合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),返回第二步。
例题如图：


" B/ L3 Z9 c# o4 A. B
数字代表最短路问题里的运费或者时间。
废话不多bb,纯手工代码如下hhhh:
6 ?# R2 I' V1 Efunction [R,T] = minways( )
%最短路问题
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;
0 b% u2 i# t5 R3 r+ h' h7 e    inf,3,inf,inf,10,inf,7;inf,inf,inf,inf,inf,inf,inf];
2 ]+ s/ k$ D2 j& [9 VR=[0,inf,inf,inf,inf,inf,inf];
0 c2 I$ G1 X6 p$ G! B1 A/ g1 TTotal=[1,2,3,4,5,6,7];
Done=[1];
0 S4 C- O- h& d- l7 l# HCandidate=[2,3,4,5,6,7];
) R# P) G- \4 g# p! N* T" D" C+ F  t/ CR(1)=0;
while (R(7)>1000)
a=length(Done);
4 p( w- I- }; D( sb=length(Candidate);
t=1;
; R1 h% {# k. _% iK={};
3 b8 f2 e: ^  ~9 q. t/ ffor i=1:a
" [- P7 Y; @- y3 n( a    for j=1:b
& L$ k$ l1 `/ t  K{t}(i,j)=R(Done(i))+D(Done(i),Candidate(j));
    end
end
if a==1
& R4 N3 U0 e1 [4 O: u( U[biaohao,number]=min(K{t});
& [( K0 v* d8 f; @+ jelse
x0=min(K{t});
[biaohao,number]=min(x0);
8 K; h! S* K9 F$ Bend
beibiaohao=Candidate(number);
Done=[Done,beibiaohao];
Candidate(Candidate==beibiaohao)=[];
R(beibiaohao)=biaohao;
t=t+1;
end
T=R(7);
! G$ W9 X# S. S3 C1 C3 \end
! {( V- m. ~4 B* j1 n
写出来了很开心！！！
也发现了matalb的矩阵是多么的调皮，不听爸爸的话！
9 ]; u  R- z2 s) d( u2 \
4 L- F- O, D' {7 q希望能给对这个问题感兴趣的提供一点微小的帮助。

yin123

在matlab中求解最短路编程