在matlab中求解最短路编程

ubeautqq

运筹学学完最短路问题心血来潮，想通过matalb编程实现一下。
$ t4 P" j/ d+ R0 x! J' _' `
# X8 ]# \! g3 R! C! U4 q算法步骤是课上学的，如下：
1.令起点标号为0，即b(s)=0,
2.找出所有已标号vi和未标号vj的弧的集合，B={(i,j)},如果这样的弧不存在或者终点vt已标号，则计算结束
5 Z2 A7 @& }. x9 _% V5 V3.计算集合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),返回第二步。
( y+ `5 e* F! W* b8 @9 ^. U+ T$ t例题如图：

% h  L6 I6 A$ O9 D& o3 _- T! L
0 X8 C, A. g* @( h
数字代表最短路问题里的运费或者时间。
  o' c; _+ _2 D5 d1 {, S/ n0 T' O废话不多bb,纯手工代码如下hhhh:
function [R,T] = minways( )
6 r* c8 A. {: O; E+ G%最短路问题
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 x8 G5 U- X. N7 y4 W# Y( @    inf,3,inf,inf,10,inf,7;inf,inf,inf,inf,inf,inf,inf];
! n8 H  s5 x& F: [: TR=[0,inf,inf,inf,inf,inf,inf];
Total=[1,2,3,4,5,6,7];
! o2 g* C8 P3 iDone=[1];
Candidate=[2,3,4,5,6,7];
R(1)=0;
while (R(7)>1000)
a=length(Done);
6 b$ D6 x$ s- ?$ Hb=length(Candidate);
t=1;
K={};
( `! e3 A$ r( i1 k8 S) ?; k. v3 Wfor i=1:a
. t0 n) _: @! U6 D+ k    for j=1:b
/ N4 r. j# F% B+ H1 T0 @: h  K{t}(i,j)=R(Done(i))+D(Done(i),Candidate(j));
    end
end
( n; Z5 ^8 v' x2 Cif a==1
9 X( D  }, L* j2 F[biaohao,number]=min(K{t});
- t+ o( U, x1 w7 ]else
2 M, S" L* d2 T% Z  O* s' ox0=min(K{t});
[biaohao,number]=min(x0);
end
beibiaohao=Candidate(number);
. k6 j9 |& o' ADone=[Done,beibiaohao];
Candidate(Candidate==beibiaohao)=[];
! F4 l$ M# H8 K5 O: F( J# vR(beibiaohao)=biaohao;
t=t+1;
end
2 r. W4 f( q. ~2 a0 ], ~5 iT=R(7);
- B* G+ }. D7 r3 bend
4 V3 M+ M# g7 c4 |
3 ?) z6 ~/ I" R8 Z写出来了很开心！！！
也发现了matalb的矩阵是多么的调皮，不听爸爸的话！
- j7 Y+ j; ?: e/ @0 Z: {: i
希望能给对这个问题感兴趣的提供一点微小的帮助。

yin123

在matlab中求解最短路编程