第五章图(四).ppt

0 1 2 3 4 5 20 30 60 65 15 20 10 80 40 35 70 图 带权有向图及其邻接矩阵 ∞ 20 60 ∞ 10 65 ∞ ∞ 30 70 ∞ ∞ ∞ ∞ ∞ 40 ∞ ∞ ∞ ∞ ∞ ∞ 35 ∞ ∞ ∞ ∞ ∞ ∞ 20 ∞ ∞ 15 80 ∞ ∞ 顶点 步骤 1 2 3 4 5 S 初态 Dist pre 20 0 60 0 ∞ 0 10 0 65 0 {0} 1 Dist pre 20 0 60 0 ∞ 0 10 0 30 4 {0, 4} 2 Dist pre 20 0 50 1 90 1 10 0 30 4 {0, 4, 1} 3 Dist pre 20 0 45 5 90 1 10 0 30 4 {0, 4, 1, 5} 4 Dist pre 20 0 45 5 85 2 10 0 30 4 {0, 4, 1, 5, 2} 5 Dist pre 20 0 45 5 85 2 10 0 30 4 {0, 4, 1, 5, 2, 3} 表 求最短路径时数组dist和pre的各分量的变化情况 ◆ 初始化为Path[i][j]=-1，表示从Vi到Vj 不经过任何(S中的中间)顶点。当某个顶点Vk加入到S中后使A[i][j]变小时，令Path[i][j]=k。 下表给出了利用Floyd算法求图的带权有向图的任意一对顶点间最短路径的过程。 图 带权有向图及其邻接矩阵 0 2 8 ∞ 0 4 5 ∞ 0 V1 4 8 2 V2 V0 5 表 用Floyd算法求任意一对顶点间最短路径 0 2 8 ∞ 0 4 5 ∞ 0 0 2 8 ∞ 0 4 5 7 0 0 2 6 ∞ 0 4 5 7 0 0 2 6 9 0 4 5 7 0 A -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 -1 -1 -1 1 -1 -1 -1 -1 0 -1 -1 -1 1 2 -1 -1 -1 0 -1 Path S { } { 0 } { 0, 1 } { 0, 1, 2 } 步骤 初态 k=0 K=1 K=2 根据上述过程中Path[i][j]数组，得出： V0到V1 ：最短路径是{ 0, 1 } ，路径长度是2 ； V0到V2 ：最短路径是{ 0, 1, 2 } ，路径长度是6 ； V1到V0 ：最短路径是{ 1, 2, 0 } ，路径长度是9 ； V1到V2 ：最短路径是{ 1, 2 } ，路径长度是4 ； V2到V0 ：最短路径是{ 2, 0 } ，路径长度是5 ； V2到V1 ：最短路径是{ 2, 0, 1 } ，路径长度是7 ； 人有了知识，就会具备各种分析能力， 明辨是非的能力。 所以我们要勤恳读书，广泛阅读， 古人说“书中自有黄金屋。 ”通过阅读科技书籍，我们能丰富知识， 培养逻辑思维能力； 通过阅读文学作品，我们能提高文学鉴赏水平， 培养文学情趣； 通过阅读报刊，我们能增长见识，扩大自己的知识面。 有许多书籍还能培养我们的道德情操， 给我们巨大的精神力量， 鼓舞我们前进。 * 第七讲 图 浙江大学 陈 越 6.6 最短路径问题 若用带权图表示交通网，图中顶点表示地点，边代表两地之间有直接道路，边上的权值表示路程(或所花费用或时间) 。从一个地方到另一个地方的路径长度表示该路径上各边的权值之和。问题： ◆ 两地之间是否有通路? ◆ 在有多条通路的情况下，哪条最短? 考虑到交通网的有向性，直接讨论的是带权有向图的最短路径问题，但解决问题的算法也适用于无向图。 将一个路径的起始顶点称为源点，最后一个顶点称为终点。 ? ? 问题分类 单源最短路径问题：从某固定源点出发，求其 到所有其他顶点的最短路径 （有向）无权图 （有向）有权图 多源最短路径问题：求任意两顶点间的最短路 径 6.6.1无权图的单源最短路算法 按照递增（非递减）的顺序找出固定顶点到各个顶点的最短路. Dijkstra算法（迪杰斯特拉） 1.无权图的单源最短路算法 0 v3 1 v1 v4 2 v2 2 v5 3 0: ? 1: ? 2: ? v3 v1 an