运筹学05_图与网络分析2-最短路_第1页
运筹学05_图与网络分析2-最短路_第2页
运筹学05_图与网络分析2-最短路_第3页
运筹学05_图与网络分析2-最短路_第4页
运筹学05_图与网络分析2-最短路_第5页
已阅读5页，还剩67页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、0P(P )min(P)路P0的权称为从vs到vt的距离，记为d(vs,vt)。11112minkllkiijijLLL vV ,vV为从v1到vk的最短路的长度，l表示在从v1到vk的最短路上，与vk相邻的点是vl4、若最后一个顶点vn未标号，则转回第2步；若vn已标号，则从vn开始，按照第一个标号逆向追踪，直到v1，就得到从v1到vn的最短路，vn的第二个标号表示最短路的长度。512756342552731357112325205127563425527313571051275634255273135710512756342552731357105127563425527313571051

2、275634255273135710351275634255273135710(1,3)512756342552731357104(1,3)51275634255273135710(2,4)(1,3)(4,4)512756342552731357107(1,3)(2,4)51275634255273135710(3,7)(1,3)(2,4)512756342552731357108(1,3)(2,4)(3,7)51275634255273135710(6,8)(1,3)(2,4)(3,7)51275634255273135710(1,3)(2,4)(3,7)(6,8)(5,13)5127563

3、4255273135710(1,3)(2,4)(3,7)(6,8)(5,13)(0)(1,1)(1,3)(3,5)(2,6)(5,10)(5,9)(5,12)v1v3v222-3(m 1)(m)1k1iikikLmin L(v ,v )ik存在弧，包括3、如果对所有的点L1k(m)= L1k(m+1）都成立则逆向追踪，找出最短路，算法终止；若存在L1k(m) L1k(m+1）,则令m=m+1，返回第2步v1v2v3v432-2-145(0)v1v2v3v432-2-145(1,2)(1,3)(2,1)(0)v1v2v3v432-2-145(3,1)(1,3)(2,0)(0)v1v2v3v432

4、-2-145(3,1)(1,3)(2,1)v8v2v4v7v5v1v3v611111123355223678终点起点v1v2v3v4v5v6v7v8t=1t=2t=3t=4v10-1-230000v2602-1-5-5-5v3-30-51-2-2-2-2v48023-7-7-7v5-101-3-3v61017-1-1-1v7-105-5-5v8-3-5066lijP(t)1jv1v2v3v4v52314153将边vi，vj看作两条弧，(vi, vj)和(vj, vi)购购置置年年份份12345单位（万元）1111121213使用年数 0-1 1-2 2-3 3-4 4-5维维修修费费用用（万万元元）5681

人人文库> 全部分类> 教育资料 > 备课教案

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论