16-L01 最短路径问题.pdfVIP

  1. 1、本文档共7页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
  5. 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
  6. 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们
  7. 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
  8. 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
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

文档评论(0)

ctuorn0371 + 关注
实名认证
文档贡献者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档