在matlab中求解最短路编程

ubeautqq

运筹学学完最短路问题心血来潮，想通过matalb编程实现一下。
- f, W5 s1 ~6 o) ^' J5 T4 `
算法步骤是课上学的，如下：
" z1 f$ @( f& I8 x3 Y2 @$ h, X1.令起点标号为0，即b(s)=0,
2.找出所有已标号vi和未标号vj的弧的集合，B={(i,j)},如果这样的弧不存在或者终点vt已标号，则计算结束
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),返回第二步。
* `* G; \3 W1 R2 B/ U9 E例题如图：
" k; \" f$ N, s9 G) h0 y
0 b) T/ W3 A4 g7 \5 S7 A" B2 i

数字代表最短路问题里的运费或者时间。
9 l- T" H1 i" B1 K# S1 W: G废话不多bb,纯手工代码如下hhhh:
" ^( p' m. x) ?+ A4 e' V8 A) x+ h0 yfunction [R,T] = minways( )
  R5 u, p$ y5 m; n, ?* N+ r+ Q%最短路问题
' R! s7 A( M0 wD=[inf,8,6,2,inf,inf,inf;inf,inf,inf,inf,5,inf,inf;inf,5,inf,2,inf,4,inf;
+ M! J8 f% _9 h1 O" a7 m4 q& Q+ M    inf,inf,3,inf,inf,2,inf;inf,inf,inf,inf,inf,inf,5;
0 B6 o; R6 W' W; a- Q    inf,3,inf,inf,10,inf,7;inf,inf,inf,inf,inf,inf,inf];
2 C4 `6 Z6 L& P/ SR=[0,inf,inf,inf,inf,inf,inf];
2 X$ V3 D2 _6 STotal=[1,2,3,4,5,6,7];
Done=[1];
Candidate=[2,3,4,5,6,7];
8 l! k1 R( _' |, t) f9 M1 [* ~4 ~3 }R(1)=0;
while (R(7)>1000)
a=length(Done);
b=length(Candidate);
t=1;
' x$ x/ Y# ]8 p1 k+ j2 L  ^K={};
3 h/ ?9 h* a6 n6 M+ m" k4 Wfor i=1:a
+ W) u" l% q7 q, c& C8 B    for j=1:b
" [* K! P2 _# G8 v  K{t}(i,j)=R(Done(i))+D(Done(i),Candidate(j));
    end
4 I: z1 ~- M2 \" q$ A2 i- d8 zend
) U! f7 c$ q5 N  z% g' Vif a==1
2 C# Z2 `7 r+ \+ _) Y[biaohao,number]=min(K{t});
else
) O* f7 H2 w: }9 Z* \x0=min(K{t});
[biaohao,number]=min(x0);
end
beibiaohao=Candidate(number);
Done=[Done,beibiaohao];
6 j4 _  K, ]% GCandidate(Candidate==beibiaohao)=[];
: j9 \4 u( |; B+ g( BR(beibiaohao)=biaohao;
t=t+1;
( v4 E, b! i. }- A! M& R0 `# oend
T=R(7);
end

& n) \/ N% l" R1 t8 w4 `; q写出来了很开心！！！
也发现了matalb的矩阵是多么的调皮，不听爸爸的话！

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

yin123

在matlab中求解最短路编程