在matlab中求解最短路编程

ubeautqq

# {+ R, _( D, g! A6 _, G$ b; @, E运筹学学完最短路问题心血来潮，想通过matalb编程实现一下。
+ m" d- y* P# C. [
算法步骤是课上学的，如下：
  j: s" p7 P! z, q2 ]9 Q0 S9 }3 U1.令起点标号为0，即b(s)=0,
2 g2 i5 g3 S) X7 J6 x4 @0 A) X$ \4 t2.找出所有已标号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),返回第二步。
. e5 z; ^% g. o' t例题如图：

6 a' g% _% x. I3 |

数字代表最短路问题里的运费或者时间。
废话不多bb,纯手工代码如下hhhh:
function [R,T] = minways( )
7 R1 j7 g# h/ h, v# C* t/ i( ?%最短路问题
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;
7 `3 ~1 D/ s; z- G- b) Q    inf,3,inf,inf,10,inf,7;inf,inf,inf,inf,inf,inf,inf];
R=[0,inf,inf,inf,inf,inf,inf];
" F! L  j2 G6 O3 g* d7 wTotal=[1,2,3,4,5,6,7];
Done=[1];
5 \' @% y* A/ E+ b8 B3 |; r! sCandidate=[2,3,4,5,6,7];
8 ?, K1 @# n, u6 F7 J. LR(1)=0;
; k: ]# j/ ~# m6 s& P8 fwhile (R(7)>1000)
a=length(Done);
b=length(Candidate);
t=1;
K={};
# L" K! n; C. s  D: Z0 v4 v" x' I, @4 d7 Bfor i=1:a
' Z% X9 K2 d# e4 R6 V  z4 a    for j=1:b
  K{t}(i,j)=R(Done(i))+D(Done(i),Candidate(j));
1 O9 Z8 ~1 L$ }8 B' B* |. r    end
end
2 e! s9 `0 n- [4 K- tif a==1
8 i& j) P6 f" x( Q3 n[biaohao,number]=min(K{t});
else
3 A" C, o; I0 w8 h3 ^1 T) V" gx0=min(K{t});
, h) l6 u* }) P$ _0 \/ d" S- d[biaohao,number]=min(x0);
end
beibiaohao=Candidate(number);
Done=[Done,beibiaohao];
1 g* Z+ a* O9 z2 t( I* Y  i& w- UCandidate(Candidate==beibiaohao)=[];
R(beibiaohao)=biaohao;
' \8 [4 c( D% H7 pt=t+1;
. U9 D' E! X/ P9 gend
T=R(7);
end

' X9 B; e5 ~2 M/ ]" P写出来了很开心！！！
% Y" c+ Z" q4 \! i也发现了matalb的矩阵是多么的调皮，不听爸爸的话！
( ~4 Q  }) q/ F) x
+ i& u6 d" W- ^1 m$ ~希望能给对这个问题感兴趣的提供一点微小的帮助。

yin123

在matlab中求解最短路编程