数据结构2_第8章2_1 算法与数据结构 课件 ppt.pptVIP

最短路径 (Shortest Path) 最短路径问题：如果从图中某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条，如何找到一条路径，使得沿此路径各边上的权值总和达到最小。 问题解法 单源最短路径 — Dijkstra算法 任意顶点对之间的最短路径 — Floyd算法 单源最短路径问题 问题的提出： 给定一个带权有向图G与源点v，求从v到G中其它顶点的最短路径。限定各边上的权值大于或等于0。 为求得这些最短路径，Dijkstra提出按路径长度的递增次序，逐步产生最短路径的算法。首先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从顶点v到其它各顶点的最短路径全部求出为止。 举例说明 拓扑排序 计划、施工过程、生产流程、程序流程等都是“工程”。除了很小的工程外，一般都把工程分为若干个叫做“活动”的子工程。完成了这些活动，这个工程就可以完成了。 例如，计算机专业学生的学习就是一个工程，每一门课程的学习就是整个工程的一些活动。其中有些课程要求先修课程，有些则不要求。这样在有的课程之间有先后关系，有的课程可以并行地学习。 进行拓扑排序的方法 关键路径 定义几个与计算关键活动有关的量： 事件Vi 的最早可能开始时间Ve(i) 是从源点V0 到顶点Vi 的最长路径长度。 事件Vi 的最迟允许开始时间Vl[i] 是在保证汇点Vn-1 在Ve[n-1] 时刻完成的前提 下，事件Vi 的允许的最迟开始时间。 活动ak 的最早可能开始时间 e[k] 设活动ak 在边 Vi , Vj 上，则e[k]是从源点 V0到顶点Vi 的最长路径长度。因此, e[k] = Ve[i]。 活动ak 的最迟允许开始时间 l[k] l[k]是在不会引起时间延误的前提下，该活动允 许的最迟开始时间。 l[k] = Vl[j] - dur(i, j)。 其中，dur(i, j)是完成ak 所需的时间。 时间余量 l[k] - e[k] 表示活动ak 的最早可能开始时间和最迟允许开始时间的时间余量。l[k] == e[k]表示活动ak 是没有时间余量的关键活动。显然，关键路径上的所有活动都是关键活动。 为找出关键活动, 需要求各个活动的 e[k] 与 l[k]，以判别是否 l[k] == e[k]. 为求得e[k]与 l[k]，需要先求得从源点V0到各个顶点Vi 的 Ve[i] 和 Vl[i]。 求Ve[i]的递推公式 从Ve[0] = 0开始，向前递推 Vi, Vj ? S2, i = 1, 2, ?, n-1 其中, S2是所有从Vi指向顶点Vj 的有向边 Vi , Vj的集合。 从Vl[n-1] = Ve[n-1]开始，反向递推 Vi, Vj ? S1, i = n-2, n-3, ?, 0 其中, S1是所有从顶点Vi 发出的有向边 Vi , Vj 的集合。 TOPOSORT(vexnode dig[]) { int i,j,k,m=0,top=-1; edgenode *p; for (i=0;in;i++) if (dig[i].id==0) { dig[i].id=top; top=i; } while (top!=-1) { j=top; top=dog[top].id; printf(“%d\t”, dig[j].vertex+1); m++; p=dig[j].link; while (p) { k=p-adjvex; dig[k].id--; if (dig[k].id==0) { dig[k].id=top; top=k; } p=p-next; } } if (mn) printf(“\nThe network has a cycle\n”); } 算法分析 设AOV网有n个顶点，e条边。初始建立入度为0 的顶点栈，要检查所有顶