有哪些信誉好的足球投注网站- 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
文档评论（0）