- 1、本文档共26页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
例 (2). 计算、修改T标号 设刚得到P标号的节点为Vi,考虑所有与Vi相联的T标号点Vj,修改Vj的T标号 (3).确定P标号 (4).重复2~3步骤,直到终点得到永久P标号。 最短路径追踪: P(V4)=P(V2)+d24,记录V2→V4 P(V2)= P(V3)+d32,记录V3→V2 P(V3)= P(V1)+d13,记录V1→V3 所以,从V1→V4的最短路径为 V1→V3→V2→V4 最短路径追踪: P(V4)=P(V2)+d24,记录V2→V4 P(V2)= P(V3)+d32,记录V3→V2 P(V3)= P(V1)+d13,记录V1→V3 所以,从V1→V4的最短路径为 V1→V3→V2→V4 计算停止判别标准: 对于求VS→Vt的最短路,Vt标上P标号时计算停止; 对于求VS→所有点的最短路,所有点标上P标号时计算停止。 对于标号法的说明 (1). 路权为负值时失效(交通网络中一般不存在) (2). 对于无向图—(将原图中的每条边视为由方向相反的两条弧组成,其权相等。 距离矩阵法 适用条件:任意点之间的最短路 1、构造距离矩阵 2、矩阵迭代计算 * * 第三节 最短路问题 一、标号法 两个固定点之间的最短路 二、距离矩阵法 任意点之间的最短路 标号法 标号法计算步骤 (1). 初始化 (永久标号P,临时标号T) 设:起点Vs,终点Vt,其他点Vi 起点Vs: P(VS)=0 其他点Vi:T(Vi)=∞ 计算停止判别标准:终点Vt获得了P标号(永久标号) V1 V2 V3 V4 6 2 1 4 8 初始化 V1标上P标号,P(V1)=0 其他节点标上T标号: T(V2)=∞, T(V3)=∞ T(V4)=∞ P(V1)=0 T(V2)=∞ T(V3)=∞ T(V4)=∞ P(Vi) V1 V2 V3 V4 6 2 1 4 8 修改T标号: V1节点为刚得到P标号的节点 与之相连的节点是V2、V3 T(V2)=min(∞,P(V1)+d12) =min(∞,0+6)=6 P(V1)=0 T(V3)=min(∞,P(V1)+d13) =min(∞,0+2)=2 P(V1)=0 T(V2)=6 T(V3)=2 T(V4)=∞ 在所有T标号节点中,选择标号最小的节点, 将其T标号改为P标号。 V1 V2 V3 V4 6 2 1 4 8 T(V4)=∞ T(V2)=6 T(V3)=2 V3节点T标号值最小, 将其修改成P标号 P(V3)=2 P(V1)=0 T(V2)=6 T(V3)=2 T(V4)=∞ P(V3)=2 V1 V2 V3 V4 6 2 1 4 8 修改T标号: V3节点为刚得到P标号的节点 与之相连的节点是V2、V4 T(V2)=min(6,P(V3)+d32) =min(6,2+1)=3 P(V3)=2 T(V4)=min(∞,P(V3)+d34) =min(∞,2+8)=10 P(V1)=0 T(V2)=3 P(V3)=2 T(V4)=10 V1 V2 V3 V4 6 2 1 8 8 T(V2)=3 T(V4)=10 V2节点T标号值最小, 将其修改成P标号 P(V2)=3 P(V1)=0 T(V2)=3 T(V4)=10 P(V3)=2 P(V2)=3 V1 V2 V3 V4 6 2 1 8 8 修改T标号: V2节点为刚得到P标号的节点 与之相连的节点是V4 T(V4)=min(10,P(V2)+d24) =min(10,3+8)=10 P(V2)=3 P(V1)=0 P(V2)=3 P(V3)=2 T(V4)=10 这时只有一个T标号节点:V4 将V4的T标号改成P标号 V1 V2 V3 V4 6 2 1 4 8 P(V4)=7 计算停止,从V1到V4的 最短路为7个单位。 P(V1)=0 P(V2)=3 P(V3)=2 T(V4)=7 P(V4)=7 最短路问题的两个结果:最短路权 最短路径 V1 V2 V3 V4 6 2 1 4 8 V1 V2 V3 V4 6 2 1 4 8 V1 V2 V3 V4 6 2 1 4 8 4 无向图的处理:将原图中的每条边视为由方向相反的两条 弧组成,其权相等 D=[dij] V1 V2 V3 V4 6 2 1 4 8 Dij的含义:当前从i节点直接到j节点的距离 3、终止判别条件 (n为节点数量)
您可能关注的文档
最近下载
- 安全生产推进小组成立文件.docx VIP
- (精)防人因培训.ppt
- 4.3 信息系统在社会应用中的优势及局限性 课件-2022-2023学年粤教版(2019)高中信息技术必修2.pptx VIP
- 2021医院必威体育官网网址培训课件.pptx
- 必威体育精装版GBT20647.9物业服务管理体系一整套文件(手册+程序文件+管理制度+表单).pdf
- 9.2 提高防护能力 2024-2025学年七年级道德与法治上册高效备课精品课件(统编版2024).pptx VIP
- xx小学学平险问题专项整治实施方案.doc
- 可靠性试验培训.ppt
- 2.3 涡流、电磁阻尼和电磁驱动 教学设计 -2024-2025学年高二下学期物理人教版(2019)选择性必修第二册.docx
- 国家建筑标准设计图集15J207-1 单层防水卷材屋面建筑构造(一)金属屋面.pdf
文档评论(0)