图Dijkstra算法和Floyed算法(PPT-150).ppt

1 算法分析 问题提出 一个无环的有向图称作有向无环图，简称DAG图。 DAG图在工程计划和管理方面应用广泛。几乎所有的工程(project)都可分为若干个称作“活动”的子工程， 并且这些子工程之间通常受着一定条件的约束。 问题提出 某些子工程必须在另外的一些子工程完成之后才能开始。对整个工程和系统，人们主要关心的是两方面的问题： （1）工程能否顺利进行； （2） 完成整个工程所必须的最短时间。 void FindInDegree(ALGraph G, int indegree[]) {int i; ArcNode *p; for (i=0;iG.VExnum;i++) {p=G.VErtices[i].firstarc; while (p) {indegree[p-adjvex]++; p=p-next; } } } 7.5.1 拓扑排序 求各顶点入度的算法详解 Status TopologicalSort(ALGraph G) { SqStack S; int count,k,i; ArcNode *p; int indegree[MAX_VERTEX_NUM]; FindInDegree(G, indegree); // 对各顶点求入度 InitStack(S); for (i=0; iG.VExnum; ++i) // 建零入度顶点栈S if (!indegree[i]) Push(S, i); // 入度为0者进栈 count = 0; // 对输出顶点计数 7.5.1 拓扑排序 拓扑排序算法详解 见下页 while (!StackEmpty(S)) { Pop(S, i); printf(i, G.VErtices[i].data); ++count; for (p=G.VErtices[i].firstarc; p; p=p-nextarc) { k = p-adjVEx; if (!(--indegree[k])) Push(S, k); } } if (countG.VExnum) return ERROR; else return OK; } // TopologicalSort 接上页 7.5.1 拓扑排序 拓扑排序算法详解 算法分析 设AOV网有n个顶点，e条边。 初始建立入度为0 的顶点栈，要检查所有顶点一次，执行时间为O(n)；排序中，若AOV网无回路，则每个顶点入、出栈各一次，每个边表结点被检查一次，执行时间为O(n+e)； 拓扑排序算法的时间复杂度为O(n+e)。 7.5.1 拓扑排序 AOE网：带权的有向图,顶点表示事件,边表示活动，权表示活动持续的时间。 7.5.2 关键路径 关键路径的有关概念 AOE网的特点 (1)表示实际工程计划的AOE网应该是无回路的; (2)只有一个入度为零的顶点(称作源点),表示整个活动开始; (3)只有一个出度为零的顶点(称作汇点)表示整个活动结束。 v1 v2 V3 v8 v9 v6 20 12 10 15 10 12 v4 v5 20 v7 2 2 2 12 7.5.2 关键路径 AOE网图示 源点 汇点 讨论： (1)整个工程需要多少时间？ (2)哪些活动是影响工程进度的关键？ v1 v2 V3 v8 v9 v6 20 12 10 15 10 12 v4 v5 20 v7 2 2 2 12 7.5.2 关键路径 AOE网图示 源点 汇点 答案： 最短时间是从源点到汇点的最长路径长度。 最长路径上的活动是影响工程进度的关键。 在AOE 网中，有些活动可以同时进行，完成一个工程所需的最短时间是从源点到汇点的最长路径长度。 长度最长的路径称为关键路