第10章 图论与网络流模型答案.docx
- 文档编号:2027895
- 上传时间:2023-05-02
- 格式:DOCX
- 页数:20
- 大小:15.10KB
第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
whilek fori=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 whilek fori=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 whilek fori=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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第10章 图论与网络流模型答案 10 网络 模型 答案