数据结构Chap7-26.ppt

* P是v、w之间的某种关联属性，比如道路交通图，孤表示v、w之间有道路相连。通信网络图，孤表达的两点之间可以通信，再如，表达债权关系图时，v到w间有狐，表示v借钱给了w，此外，我们还可以给弧上加权，来进一步表达借了多少钱。等等 带权有向图 0 5 1 2 3 4 100 30 60 10 10 5 50 20 最短路径 长度 （v0，v2） 10 （v0，v4） 30 （v0，v4，v3） 50 （v0,v4,v3,v5) 60 v0→v1 无 一、求某顶点到其余各点的最短路径 依最短路径的长度递增的次序, 逐个产生各最短路径。 1、迪杰斯特拉(Dijkstra)算法基本思想: 设有带权的有向图D=(V,{E})，D中的边权为 W(e)。已知源点为v0，求v0到其它各顶点的最短路径。 * 源点 v1 … 假设图中所示为从源点到其余各点之间的最短路径,则在这些路径中,必然存在一条长度最短者 v2 1)第一条(长度最短的)最短路径的特点： 在这条路径上，必定只含一条弧, 并且这条弧的权值最小。(设为v0 → vi) * 2)下一条(长度次短的)最短路径的特点： 它只可能有两种情况：或者是直接从源点到该点vj(只含一条弧);或者是从源点经过顶点vi,再到达vj(由两条弧组成)。 3)再下一条长度次短的最短路径特点: 它可能有两种情况：或者是直接从源点到该点(只含一条弧)； 或者是从源点经过顶点vi、 vj再到达该顶点(由多条弧组成)。 其余依次类推 * 假设dist[k]表示当前所求得的从源点到顶点k的最短路径 则一般情况下， dist[k]=源点到顶点k的弧上的权值 或者=源点到其他顶点的最短路径长度 +其它顶点到顶点k弧上的权值 2、 迪杰斯特拉算法的实现 * 一、存储结构 1、带权邻接矩阵cost： 用cost[i，j]表示弧〈vi，vj〉上的权。 2、顶点分为两组：S，V-S， S 中存放已求得最短路径的终点的集合。 3、辅助一维数组dist： dist[i] 表示源点到vi的最短路径长度 * 二、最短路径 1、第一条最短路径 dist[j]=min{dist[i] |vi∈V-S} 最短路径（v，vj），S=S∪ {vj} 2、修改V-S中顶点的dist值 dist[i]=min{dist[i]，dist[j]+cost[j，i]} vi ∈V-S 3、下一条最短路径 dist[j]=min {dist[i] | vi∈V-S} 4、vj并入集合S，重复2，3，直到v出发 可以到达的所有顶点都包含在S中。 * 最短路径 长度 （v0, v2） 10 （v0, v4） 30 （v0, v4, v3） 50 （v0,v4,v3,v5) 60 v0→v1 无 终点 dist[i] 集合S V1 V2 V3 V4 V5 1 2 3 4 5 5 2 4 100 30 60 10 10 5 50 20 3 1 0 //////// //////// //////// //////// ∞ 0,2,4,3,5,1 60(V0,V4,V3,V5) //////// //////// //////// ∞ 0,2,4,3,5 90(V0,V4,V5) //////// 50(V0,V4,V3) //////// ∞ 0,2,4,3 100(V0,V5) 30(V0,V4) 60(V0,V2,V3) //////// ∞ 0,2,4 100(V0,V5) 30(V0,V4) ∞ 10(V0,V2) ∞ 0,2 √ √ √ √ √ * 0 7.6 拓扑排序 * 有向无环图, 简称 DAG(directed acycline graph), 它可以表示一个工程或系统的流程图, 也可以表示学生的选课关系。 这样的有向图必须是无环的, 才能保证工程顺利进行, 而判定有向图是否无环较复杂，为此采用拓扑排序或逆拓扑排序的方法验证之。 * 用顶点表示活动，用弧表示活动间的优先关系的有向无环图，称为顶点表示活动的网(Activity On Vertex Network), 简称AOV-网。 如下页的课程关系表，若用顶点表示课程，弧表示先决条件，则课程关系可用一个有向无环图表示。 * C1 高等数学 C2