第10章 图论与网络流模型答案.docx
《第10章 图论与网络流模型答案.docx》由会员分享，可在线阅读，更多相关《第10章 图论与网络流模型答案.docx（20页珍藏版）》请在冰点文库上搜索。
第10章图论与网络流模型答案
第一题：
>>w=[050inf402510;
5001520inf25;
inf1501020inf;
40201001055;
25inf2010055;
1025inf25550;]
n=size（w,1）;
w1=w（1,:
）;
fori=1:
n
l（i）=w1（i）;
z（i）=1;
end
s=[];
s
（1）=1;
u=s
（1）;
k=1
l
z
whilekfori=1:
n
forj=1:
k
ifi~=s（j）
ifl（i）>l（u）+w（u,i）
l（i）=l（u）+w（u,i）;
z（i）=u;
end
end
end
end
l
z
ll=l;
fori=1:
n
forj=1:
k
ifi~=s（j）
ll（i）=ll（i）;
else
ll（i）=inf;
end
end
end
lv=inf;
fori=1:
n
ifll（i）lv=ll（i）;
v=i;
end
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=
050Inf402510
z=
111111
l=
050Inf402510
z=
111111
lv=
10
v=
6
s=
16
k=
2
u=
6
l=
035Inf352510
z=
161611
lv=
25
v=
5
s=
165
k=
3
u=
5
l=
03545352510
z=
165611
lv=
35
v=
2
s=
1652
k=
4
u=
2
l=
03545352510
z=
165611
lv=
35
v=
4
s=
16524
k=
5
u=
4
l=
03545352510
z=
165611
lv=
45
v=
3
s=
165243
k=
6
u=
3
l=
03545352510
z=
165611
第二题：
>>w=[0310infinfinfinfinf;
30inf5infinfinfinf;
10inf06infinfinfinf;
inf5604infinfinf;
infinfinf4095inf;
infinfinfinf9034;
infinfinf05306;
infinfinfinfinf460]
n=size（w,1）;
w1=w（1,:
）;
fori=1:
n
l（i）=w1（i）;
z（i）=1;
end
s=[];
s
（1）=1;
u=s
（1）;
k=1
l
z
whilekfori=1:
n
forj=1:
k
ifi~=s（j）
ifl（i）>l（u）+w（u,i）
l（i）=l（u）+w（u,i）;
z（i）=u;
end
end
end
end
l
z
ll=l;
fori=1:
n
forj=1:
k
ifi~=s（j）
ll（i）=ll（i）;
else
ll（i）=inf;
end
end
end
lv=inf;
fori=1:
n
ifll（i）lv=ll（i）;
v=i;
end
end
lv
v
s（k+1）=v
k=k+1
u=s（k）
end
l
z
w=
0310InfInfInfInfInf
30Inf5InfInfInfInf
10Inf06InfInfInfInf
Inf5604InfInfInf
InfInfInf4095Inf
InfInfInfInf9034
InfInfInf05306
InfInfInfInfInf460
k=
1
l=
0310InfInfInfInfInf
z=
11111111
l=
0310InfInfInfInfInf
z=
11111111
lv=
3
v=
2
s=
12
k=
2
u=
2
l=
03108InfInfInfInf
z=
11121111
lv=
8
v=
4
s=
124
k=
3
u=
4
l=
0310812InfInfInf
z=
11124111
lv=
10
v=
3
s=
1243
k=
4
u=
3
l=
0310812InfInfInf
z=
11124111
lv=
12
v=
5
s=
12435
k=
5
u=
5
l=
03108122117Inf
z=
11124551
lv=
17
v=
7
s=
124357
k=
6
u=
7
l=
0310812201723
z=
11124757
lv=
20
v=
6
s=
1243576
k=
7
u=
6
l=
0310812201723
z=
11124757
lv=
23
v=
8
s=
12435768
k=
8
u=
8
l=
0310812201723
z=
11124757
第三题：
>>w=[01infinfinfinfinfinf;
1032infinfinfinf;
inf30inf1infinfinf;
inf2inf0infinf2inf;
infinf1inf062inf;
infinfinfinf60inf3;
infinfinf22inf04;
infinfinfinfinf340]
n=size（w,1）;
w1=w（1,:
）;
fori=1:
n
l（i）=w1（i）;
z（i）=1;
end
s=[];
s
（1）=1;
u=s
（1）;
k=1
l
z
whilekfori=1:
n
forj=1:
k
ifi~=s（j）
ifl（i）>l（u）+w（u,i）
l（i）=l（u）+w（u,i）;
z（i）=u;
end
end
end
end
l
z
ll=l;
fori=1:
n
forj=1:
k
ifi~=s（j）
ll（i）=ll（i）;
else
ll（i）=inf;
end
end
end
lv=inf;
fori=1:
n
ifll（i）lv=ll（i）;
v=i;
end
end
lv
v
s（k+1）=v
k=k+1
u=s（k）
end
l
z
w=
01InfInfInfInfInfInf
1032InfInfInfInf
Inf30Inf1InfInfInf
Inf2Inf0InfInf2Inf
InfInf1Inf062Inf
InfInfInfInf60Inf3
InfInfInf22Inf04
InfInfInfInfInf340
k=
1
l=
01InfInfInfInfInfInf
z=
11111111
l=
01InfInfInfInfInfInf
z=
11111111
lv=
1
v=
2
s=
12
k=
2
u=
2
l=
0143InfInfInfInf
z=
11221111
lv=
3
v=
4
s=
124
k=
3
u=
4
l=
0143InfInf5Inf
z=
11221141
lv=
4
v=
3
s=
1243
k=
4
u=
3
l=
01435Inf5Inf
z=
11223141
lv=
5
v=
5
s=
12435
k=
5
u=
5
l=
01435115Inf
z=
11223541
lv=
5
v=
7
s=
124357
k=
6
u=
7
l=
014351159
z=
11223547
lv=
9
v=
8
s=
1243578
k=
7
u=
8
l=
014351159
z=
11223547
lv=
11
v=
6
s=
12435786
k=
8
u=
6
l=
014351159
z=
11223547
升级会员 