- 1、本文档共7页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
16-L01 最短路径问题
离散数学基础
离散数学基础
2017-11-19
• 单元内容提示
− 图的网络 (边赋权图)
− 最短路径问题
− Dijstra 算法
− Warshall 算法
• 定义. 网络 (赋权图)
− 有向图 G =(V, A) 中,V ={v , v , …, v } 。给图的每条边 a=(v , v )∈A 赋予一个实
1 2 n i j
数权 w(v , v ),得到一个有向网络 (G, w)。
i j
−通常情况下默认 w(v , v ) ≥ 0 。为简化讨论,无特别声明情况下,假定 w(v , v )
i j i j
0 。
− 当 G 是一个无向图时,类似定义一个无向网络 (G, w)。
• 定义. 距离矩阵
−对上述有向网络 (G, w),n=|V| ,定义网络的距离矩阵 D =(d ) ,
ij n×n
w(v , v ) 当 (v , v ) ∈A
di j { ∞ i j 其它i j
− 类似可以定义无向网络的距离矩阵。
• 定义. 子集和结点间的距离
−对上述网络,S⊂V , v ∈V‐S 。S 到 v 的距离定义为:
j j
d(S, v )=min{d | v ∈S}
j ij i
− v 到 S 的距离定义为:
j
d(v , S)=min{d | v ∈S}
j ji i
• 定义. 带权路径长度
− 设路径 u , u , … , u (u ∈V) 为上述网络的路径 (初等道路),其带权路径长度定
1 2 k i
义为
k−1
π(u , u ) ∑w(u , u )
1 k i i+1
i 1
• 定义. 两个结点间的最短距离
−对上述网络,结点 v 到 v 可达时, v 到 v 的所有路径中具有最小带权路径
i j i j
长度者称为 v 到 v
您可能关注的文档
最近下载
- U校园-新一代大学英语(提高篇)综合教程1和2(全).pdf VIP
- 零星维修工程服务方案.pptx
- 地理试讲逐字稿 (一).pdf VIP
- 2011年滁州市中学高级教师专业技术职务任职资格评审通过人....DOC VIP
- 中国铁路总公司关于取消铁路建设项目开工报告审批的通知,铁总计统[2015]252号.pdf VIP
- 标准图集-提灌站建设项目施工图.pdf VIP
- 18K802图集—暖通空调系统的检测与监控(水系统分册).pdf VIP
- 大学发展心理学考试(习题卷1).pdf VIP
- 泌尿、男性生殖系统.ppt VIP
- 建筑工程图集 12R11612K512:污水源热泵系统设计与安装.pdf VIP
文档评论(0)