图及应用.ppt

图的一些典型算法 最小生成树 最短路径 拓扑排序 关键路径 Sample Input 　　6 9　　 1 2 2　　 1 3 2　　 2 3 3　　 3 4 3　　 1 5 1　　 2 6 3　　 4 5 4　　 4 6 7　　 5 6 6　　 1 3　　 2 3　　 3 4　　 4 5　　 4 6 dijkstra算法（从一个顶点到其余各顶点的最短路径，单源最短路径） 对于一个含有n个顶点和e条边的图来说，从某一个顶点Vi到其余任一顶点Vj的最短路径，可能是它们之间的边（Vi，Vj），也可能是经过k个中间顶点和k+1条边所形成的路径(1≤k≤n-2)。 1、先求出从源点Vs到其余顶点的路径长度，放在dist数组中，找出其值最小的元素（假设为dist[m]），该元素值就是从源点Vs到终点Vm的最短路径长度，把Vm并入集合S中。 2、以Vm作为新考虑的中间顶点，对S以外的每个顶点Vj，比较dist[m]+G[m,j]与dist [j]的大小，若前者小，表明加入了新的中间顶点后可以得到更好的方案，即可求得更短的路径，则用它代替dist[j] 。 3、重复以上过程n-2次，即可在dist数组中得到从源点到其余各终点的最段路径长度。 原则： 按从源点Vi到其余每个顶点的最短路径的升序依次求出从源点到各顶点的最短路径长度。 方法： （1）找出中间点Vj （★） （2）用Vi到Vj的最短路径长度作为参照对其余结点进行比较、修改 （3）重复n-2次 SPFA算法（求单源最短路径） Pascal伪代码: Procedure SPFA; Begin initialize-single-source(G,s); initialize-queue(Q); enqueue(Q,s); while not empty(Q) do begin u:=dequeue(Q); for each v∈adj[u] do begin tmp:=d[v]; relax(u,v); if (tmpd[v]) and (not v in Q) then enqueue(v); end; end; End; SPFA算法注意事项： 1.无向图中，一定要把检查过的边删除，不然会重新检查，形成死循环！ 2.图中一定不能存在负权回路！！ 如何判定回路，我们在下面的拓扑排序中进行详解！ （1）是一种动态规划算法 邻接矩阵A[I,j]：vi—vj当前最短路径 以每个顶点Vk作为中间点，针对每对顶点vi到 vj的当前最短路径进行调整 A[i,j]=min(a[i,j],a[i,k]+a[k,j]) （2）优点：容易理解，可以算出任意两个节点之间 的最短距离，代码编写简单； 　 缺点：时间复杂度比较高，不适合计算大量数 据。 0(n3) 最短路径算法总结： 最短路径问题的求解还不止这几种算法，比如还有Bellman-Ford算法、分枝定界等等，而且大家也可以创造出各种各样的新算法来。不同的最短路径问题到底用哪种算法，以及还需要对该种算法作什么改动，是非常重要的，这种能力往往是很多同学所欠缺的，这需要大家在平常的训练中多做这类题目，还要多总结，以达到熟能生巧的境界。 Dijkstra算法的效率高,但是也有局限性,就是对于含负权的图无能为力. SPFA算法效率很不错,而且对于最短路长存在的图都适用,无论是否存在负权边. 它的编程复杂度也很低,是性价比极高的算法. 在不含负权的图中,特别是在边数稠密的图中,我们常常选择Dijkstra算法; 在稀疏图中,二叉堆实现的Dijkstra算法也是不错的选择,SPFA算法效率极高; 在图中含有负权,稀疏图随便用后两种算法中的哪一种都行,因为它们的效率都可以接受,而且很容易写; 如果是稠密图,就非SPFA算法莫属了. 权：设bi 表示设备在第i 年年初的购买费,Ci 表示设备使用i 年后的维修费, 例2 Bessie 来到一个小农场，有时她想回老家看看她的一位好友。她不想太早地回到老家，因为她喜欢途中的美丽风景。她决定选择次短路径，而不是最短路径。 农村有 R (1 = R = 100,000) 条双向的路，每条路连接 N (1 = N = 5000) 个结点中的两个。结点的编号是 1..N。Bessie 从结点 1出发，她的朋友（目的地）在结点 N。 次短路径可以使用最