第10章 图论与网络流模型答案文档格式.docx

第10章 图论与网络流模型答案文档格式.docx

《第10章 图论与网络流模型答案文档格式.docx》由会员分享，可在线阅读，更多相关《第10章 图论与网络流模型答案文档格式.docx（20页珍藏版）》请在冰点文库上搜索。

n

l（i）=w1（i）;

z（i）=1;

end

s=[];

s

（1）=1;

u=s

（1）;

k=1

l

z

whilek<

forj=1:

k

ifi~=s（j）

ifl（i）>

l（u）+w（u,i）

l（i）=l（u）+w（u,i）;

z（i）=u;

ll=l;

ifi~=s（j）

ll（i）=ll（i）;

else

ll（i）=inf;

lv=inf;

ifll（i）<

lv

lv=ll（i）;

v=i;

end

lv

v

s（k+1）=v

k=k+1

u=s（k）

end

l

z

w=

050Inf402510

5001520Inf25

Inf1501020Inf

40201001055

25Inf2010055

1025Inf25550

k=

1

l=

z=

111111

lv=

10

v=

6

s=

16

2

u=

035Inf352510

161611

25

5

165

3

03545352510

165611

35

1652

4

16524

45

165243

165611

第二题：

w=[0310infinfinfinfinf;

30inf5infinfinfinf;

10inf06infinfinfinf;

inf5604infinfinf;

infinfinf4095inf;

infinfinfinf9034;

infinfinf05306;

infinfinfinfinf460]

0310InfInfInfInfInf

30Inf5InfInfInfInf

10Inf06InfInfInfInf

Inf5604InfInfInf

InfInfInf4095Inf

InfInfInfInf9034

InfInfInf05306

InfInfInfInfInf460

11111111

12

03108InfInfInfInf

11121111

8

124

0310812InfInfInf

11124111

1243

12

12435

03108122117Inf

11124551

17

7

124357

0310812201723

11124757

20

1243576

23

12435768

第三题：

w=[01infinfinfinfinfinf;

1032infinfinfinf;

inf30inf1infinfinf;

inf2inf0infinf2inf;

infinf1inf062inf;

infinfinfinf60inf3;

infinfinf22inf04;

infinfinfinfinf340]

01InfInfInfInfInfInf

1032InfInfInfInf

Inf30Inf1InfInfInf

Inf2Inf0InfInf2Inf

InfInf1Inf062Inf

InfInfInfInf60Inf3

InfInfInf22Inf04

InfInfInfInfInf340

0143InfInfInfInf

11221111

0143InfInf5Inf

11221141

01435Inf5Inf

11223141

01435115Inf

11223541

014351159

11223547

9

1243578

11

12435786