在matlab中求解最短路编程

ubeautqq

4 ?5 W1 `5 o  n- A2 J8 F运筹学学完最短路问题心血来潮，想通过matalb编程实现一下。

算法步骤是课上学的，如下：
1.令起点标号为0，即b(s)=0,
2.找出所有已标号vi和未标号vj的弧的集合，B={(i,j)},如果这样的弧不存在或者终点vt已标号，则计算结束
3.计算集合B中弧k(i,j)=b(i)+d(i,j)的标号
7 i4 ?4 h! l, q' |, {4.选一个点标号，b(l)=min{k(i,j)|(i,j)属于B},在最小的k(i,j)的终点j处标号b(l),返回第二步。
例题如图：

2 R( y* T5 ]8 x, h* ~
& ^  V1 ]* ?0 `" o# b
: ?$ z# R3 I. v* ^- {数字代表最短路问题里的运费或者时间。
废话不多bb,纯手工代码如下hhhh:
/ v  G, O0 h% T9 T1 x8 U9 }1 W; ofunction [R,T] = minways( )
# Y8 [( n4 A4 k$ w  `%最短路问题
D=[inf,8,6,2,inf,inf,inf;inf,inf,inf,inf,5,inf,inf;inf,5,inf,2,inf,4,inf;
1 |+ c3 m' u) Y0 W  U    inf,inf,3,inf,inf,2,inf;inf,inf,inf,inf,inf,inf,5;
$ L' \7 p8 q# S    inf,3,inf,inf,10,inf,7;inf,inf,inf,inf,inf,inf,inf];
R=[0,inf,inf,inf,inf,inf,inf];
Total=[1,2,3,4,5,6,7];
Done=[1];
6 @; ?2 F# T2 x; m. mCandidate=[2,3,4,5,6,7];
R(1)=0;
while (R(7)>1000)
7 o" z2 g) i; j  ua=length(Done);
b=length(Candidate);
t=1;
K={};
1 S& A. Q7 w% R$ V4 w2 n0 ofor i=1:a
    for j=1:b
  K{t}(i,j)=R(Done(i))+D(Done(i),Candidate(j));
    end
end
& l, E9 N  q- C/ k0 w- iif a==1
[biaohao,number]=min(K{t});
9 v. E- e; i5 D& k+ ?5 ielse
x0=min(K{t});
5 p! o) x- Y: K2 g2 p! t/ M/ E% X7 m3 J[biaohao,number]=min(x0);
end
6 j, m: {8 N" v. ?beibiaohao=Candidate(number);
Done=[Done,beibiaohao];
Candidate(Candidate==beibiaohao)=[];
R(beibiaohao)=biaohao;
t=t+1;
2 J+ I( o* q/ r  ?7 ]4 m2 oend
+ ?" U8 p0 k' x5 L$ X+ BT=R(7);
end

+ |! v; [9 o' x$ _写出来了很开心！！！
也发现了matalb的矩阵是多么的调皮，不听爸爸的话！
% B6 w5 a8 J  a1 R4 z7 \
希望能给对这个问题感兴趣的提供一点微小的帮助。

yin123

在matlab中求解最短路编程