图论基本算法.pptVIP

2、Floyd算法：求任意一对顶点之间的最短路径。 [问题分析] 一是分别以图中的每个顶点为源点共调用n次Dijkstra算法，这种算法的时间复杂度为O（n3），前提条件是图中所有边的权值为非负数； 二是Floyd（弗洛伊德）算法，思路简单，时间复杂度仍然为O（n3），但可以求解任意边权的所有顶点之间的最短路径。 Floyd算法介绍： GA：存储n个顶点图的邻接矩阵 A : 表示每对顶点之间最短路径长度的二维数组， P : 记录最短路径，其元素类型为集合类型set of 1..n。 Ak[i,j]表示从顶点i到顶点j的边数不超过k条的最短路径的长度 初始化：A1[i,i]=0, A1[i,j]=GA[i,j] 之后不断尝试往已有的最短路中加入中间顶点来优化 即递推公式为： Ak[i,j] = min{Ak-1[i,j], Ak-1[i,k]+GA[k,j]} k=0,1,……,n-1 V0 V1 V2 4 11 6 2 3 D D(-1) D(0) D(1) D(2) 0 1 2 0 1 2 0 1 2 0 1 2 0 0 4 11 0 4 11 0 4 6 0 4 6 1 6 0 2 6 0 2 6 0 2 5 0 2 2 3 ∞ 0 3 7 0 3 7 0 3 7 0 P 0 1 2 0 1 2 0 1 2 0 1 2 0 AB AC AB AC AB ABC AB ABC 1 BA BC BA BC BA BC BCA BC 2 CA CA CAB CA CAB CA CAB （1）邻接矩阵A[I,j]：vi—vj当前最短路径 （2）以每个顶点Vk作为中间点，针对每对顶点vi到vj的当前最短路径进行调整 （3）A[i,j]=min(a[i,j],a[i,k]+a[k,j]) （4）0(n3) Floyd算法总结: Procedure Floyd(G，A，P)； Begin For i:=1 To n Do {初始化} For j:=1 To n Do Begin A[i,j]:=G[i,j]； If A[i,j]maxint Then p[i,j]:=[i]+[j] Else p[i,j]:=[ ]； End； For k:=1 To n Do {n次运算} For i:=1 To n Do For j:=1 To n Do {找到更短路径、保存} End； If A[i,k]+A[k,j]A[i,j] Then Begin A[i,j]：= A[i,k]+A[k,j]； P[i,j]：= P[i,k]+P[k,j]； End； 最短路径算法总结： Dijkstra算法的效率高,但是也有局限性,就是对于含负权的图无能为力. SPFA算法效率很不错,而且对于最短路长存在的图都适用,无论是否存在负权边. 它的编程复杂度也很低,是性价比极高的算法. 在不含负权的图中,特别是在边数稠密的图中,我们常常选择Dijkstra算法; 在稀疏图中,二叉堆实现的Dijkstra算法也是不错的选择,SPFA算法效率极高; 在图中含有负权,稀疏图随便用后两种算法中的哪一种都行,因为它们的效率都可以接受,而且很容易写; 如果是稠密图,就非SPFA算法莫属了. H城是一个旅游胜地，每年都有成千上万的人前来观光。为方便游客，巴士公司在各个旅游景点及宾馆，饭店等地都设置了巴士站并开通了一些单程巴士线路。每条单程巴士线路从某个巴士站出发，依次途经若干个巴士站，最终到达终点巴士站。 一名旅客最近到H城旅游，他很想去S公园游玩，但如果从他所在的饭店没有一路巴士可以直接到达S公园，则他可能要先乘某一路巴士坐几站，再下来换乘同一站台的另一路巴士, 这样换乘几次后到达S公园。 现在用整数1,2,…N 给H城的所有的巴士站编号，约定这名旅客所在饭店的巴士站编号为1,S公园巴士站的编号为N。 写一个程序，帮助这名旅客寻找一个最优乘车方案,使他在从饭店乘车到S公园的过程中换车的次数最少。 例4、最优乘车 问题描述： 输入: 第一行有两个数字M和N(1=M=100 1N=500），表示开通了M条单程巴士线路，总共有N个车站。从第二行到第M+1行依次给出了第1条到第M条巴士线路的信息。其中第i+1行给出的是第i条巴士线路的信息，从