数据结构chapter图的应用：最短路径问题,关键路径.pptVIP

* 首先，我们可以发现有这样一个事实：如果P是G中从vs到vj的最短路，vi是P中的一个点，那么，从vs沿P到vi的路是从vs到vi的最短路。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。 一种用永久和临时标号方式，一种是用OPEN, CLOSE表方式，Drew为了和下面要介绍的 A* 算法和 D* 算法表述一致，这里均采用OPEN,CLOSE表的方式。 　　其采用的是贪心法的算法策略 　　大概过程： 　　创建两个表，OPEN, CLOSE。 　　OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。 　　1． 访问路网中距离起始点最近且没有被检查过的点，把这个点放入OPEN组中等待检查。 　　2． 从OPEN表中找出距起始点最近的点，找出这个点的所有子节点，把这个点放到CLOSE表中。 　　3． 遍历考察这个点的子节点。求出这些子节点距起始点的距离值，放子节点到OPEN表中。 　　4． 重复第2和第3步,直到OPEN表为空，或找到目标点。 * Dijkstra算法的具体做法： 一开始第一组S只包括顶点v0，第二组包括其它所有顶点； v0对应的距离值为0，而第二组的顶点对应的距离值这样确定： 若图中有边v0，Vi或者（v0，Vi），则Vi的距离值为此边所带的权，否则Vi的距离值为∞。 然后，每次从第二组的顶点中选一个其距离值为最小的顶点Vu加入到第一组中； 每往第一组加入一个顶点Vu，就要对第二组的各顶点的距离值进行一次修正： 若加进Vm做中间顶点，使从s到Vi的最短路径比不加Vm的为短，则需要修改Vi的距离值。 修改后再选距离值最小的顶点加入到第一组中，如此进行下去，直到图的所有顶点都包括在第一组中或者再也没有可加入到第一组的顶点存在。 * E=n(n-1)/2 * Floyd-Warshall 算法用来找出每对点之间的最短距离。它需要用邻接矩阵来储存边，这个算法通过考虑最佳子路径来得到最佳路径。 　　注意单独一条边的路径不一定是最佳路径。 　　从任意一条单边路径开始。所有两点之间的距离是边的权，或者无穷大，如果两点之间没有边相连。 　　对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。 　　不可思议的是，只要安排适当，就能得到结果。 即使问题是求单源最短路径，还是推荐使用这个算法，如果时间和空间允许(只要有放的下邻接矩阵的空间，时间上就没问题)。 * void Floyd(AdjMGraph G,int *distance,int *path) { int i,j,k,n=G.Vertices.size; for (i=0;in;i++)//初始化 for(j=0;jn;j++) { distance[i][j]=G.edge[i][j]; if(distance[i][j] MaxWeight) path[i][j] = i; else path[i][j] = -1; } for(k=0;kn;k++) for(i=0;in;i++) for(j=0;jn;j++) if(distance[i][j]distance [i][k]+distance [k][j]) { distance[i][j]=distance [i][k]+distance [k][j]; path[i][j]=k; } } * AOV网与AOE网有密切关系又有不同。如果用他们表示工程，AOV网表示各个子工程之间的优先关系，是定性关系；在AOE网中还要体现完成各个子工程的确切时间，是定量关系。 在AOE网中，只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始。只有在进入每顶点的各有向边所代表的活动都已经结束后，该顶点所代表的事件才能发生。 在一个表示工程的AOE网中，应该不存在回路，网中仅存在一个入度为零的顶点，称作开始顶点，它表示了整个工程的开始；网中仅存在一个出度为零的顶点，称为结束顶点，它表示整个工程的结束。 由于AOE网中某些子工程（活动）可以同时进行，要保证每个子工程都能完成，完成该工程的最少时间就是该工程AOE网的关键路径长度。 4.活动的最早开始时间 活动aj的最早开始时间e (j)是该活动的起点所表示的事件最早发生时间,如果由边(vi,vk)表示活动aj,则有e(j)=ve(i)。 5.事件的最迟发生时间 事件vk的最迟发生时间