离散数学及应用 课件 5.4 最短路径,关键路径与着色_第1页
离散数学及应用 课件 5.4 最短路径,关键路径与着色_第2页
离散数学及应用 课件 5.4 最短路径,关键路径与着色_第3页
离散数学及应用 课件 5.4 最短路径,关键路径与着色_第4页
离散数学及应用 课件 5.4 最短路径,关键路径与着色_第5页
已阅读5页，还剩7页未读， 继续免费阅读

付费下载

下载本文档

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

文档简介

DiscreteMathematics鄢小虎

离散数学25.4

最短路径,关键路径与着色带权图最短路径与Dijkstra算法关键路径着色问题最短路径我们日常生活中经常用到最短路径，例如：坐地铁从深圳北站去宝安机场，怎么走最短？最短路径最短（最快、最便宜）航空路线？5最短路径带权图G=<V,E,w>,其中w:ER.

e

E,w(e)称作e的权.e=(vi,vj),记w(e)=wij.若vi,vj不相邻,记wij=.通路L的权:L的所有边的权之和,记作w(L).u和v之间的最短路径:u和v之间权最小的通路.例

L1=v0v1v3v5,w(L1)=1+7+2=10,L2=v0v1v4v5,w(L2)=12,L3=v0v2v4v5,w(L3)=11.6标号法(E.W.Dijkstra,1959)设带权图G=<V,E,w>,其中

e

E,w(e)0.设V={v1,v2,,vn},求v1到其余各顶点的最短路径1.令l1

0,p1

,lj

+

,pj

,j=2,3,

,n,P={v1},T=V-{v1},k

1,t

1./

表示空2.对所有的vj

T且(vk,vj)

E

令l

min{lj,lk+wkj},

若l=lk+wkj,则令lj

l,pj

vk.3.求li=min{lj|vj

Tt}.

令P

P

{vi},T

T-{vi},k

i.4.令t

t+1,

若t<n,则转2.视频讲解：/video/BV1Ut41197ae7Dijkstra标号法实例例

求v0到v5的最短路径t

v0

v1

v2

v3

v4

v5

1(0,

)*(+

,

)(+

,

)(+

,

)(+

,

)(+

,

)2(1,v0)*(4,v0)(+

,

)(+

,

)(+

,

)3(3,v1)*(8,v1)(6,v1)(+

,

)4(8,v1)(4,v2)*(+

,

)5(7,v4)*(10,v4)6(9,v3)*v0到v5的最短路径:v0v1v2v4v3v5,d(v0,v5)=98课堂练习计算顶点a到f的最短路径9课前复习无向图的关联矩阵有向图的关联矩阵有向图的邻接矩阵有向图的可达矩阵Dijkstra算法

10关键路径关键路径:项目网络图中从始点到终点的最长路径西天取经的关键路径11关键路径关键路径求法:/video/BV1EQ4y1v7iV?from=search&seid=13125558254989660218&spm_id_from=333.337.0.0着色问题定义

设无向图G无环,对G的每个顶点涂一种颜色，使相邻的顶点涂不同的颜色，称为图G的一种点着色,简称着色．若能用k种颜色给G的顶点着色，则称G是k-可着色的．图

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

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

最新文档

评论

0/150

提交评论