数据结构——最短路一.ppt

问题背景 最短路是实际应用中最常遇到的任务。 旅游： 长春?杭州，路程、时间、费用 最短路问题：在给定的图中，从某顶点出发，找从该点到其它顶点 cost 最小的路径。路径的cost 指该路径边的权值累加和。 最短路问题分类 两个顶点间的最短路：从一个指定的顶点到达另一指定顶点的最短路问题。 单源最短路(Single Source Shortest Path,SSSP )：从一个指定的顶点到其它所有顶点的最短路径问题。 任意顶点间的最短路：所有顶点间的最短路； 1. 无权图的单源最短路 无权——相当于所有边的权值都为 1. 源点到各顶点的路径长度：所经历的边的数目 思想：从源点开始由近及远依次求各顶点的最短路径 算法思想 设Di为源点S到顶点i的最短路径长度 ①访问初始顶点S，即令DS=0。 ②从S出发，找最短路径为1的顶点，即S的所有邻接顶点w，令Dw=DS+1 ③从上步访问的顶点w出发，找最短路径为2的顶点，即w未被访问的邻接顶点v，令Dv=Dw+1 ④继续上述过程，直至处理完所有顶点。 上述过程中，访问顶点的次序与对图进行广度优先遍历的次序是一致的; 算法实现 图采用邻接表存储； 用队列保存待处理顶点； 使用数组dist[ ]存储最短路径值。 源点初始化为0，其它初始为-1. 当dist[i] 从 -1 变为非负时，表示从源点到i的最短路径已求完 为找到最短路径，可用path[ ]存储从源点到顶点 i 的最短路上 i 之前的顶点。 算法描述 算法ShortestPath(v) /*计算从顶点v到其他各顶点的最短路径*/ S1[初始化] CREATQuene(Q) . /* 创建一个队列 */ for( i =1 ; i = n ; i ++){ path[i] = -1; dist[i] = -1. } dist[v] = 0 ; Q.inset(v)；　 S2[求从顶点v到其他各顶点的最短路径] while ( ！Q.empty() ) { u = Q.delete() ; /* 队头顶点u出队 */ for( p = Head[u].adjacent ; p ; p = p-link ){ k = p - VerAdj ; if (dist[k] == -1) { Q.insert(k);// u未访问的邻接顶点入队 dist[k] = dist[u] + 1; path[k] = u; } } } ? 算法分析 邻接表：在最短路径的计算中，一个顶点入队出队各一次，时间复杂性为O(n)；而对每个顶点，都要对它的边链表进行遍历，其遍历邻接表的开销为O(e)，于是整个算法的时间复杂性为O(n+e)。 邻接矩阵：O( n2 ) 2. 非负权图的单源最短路 给定一个带权图G与源点v，求从v到G中其它顶点的最短路径。要求各边的权值为非负实数。 无权最短路算法？ 分析 方法一：枚举从源点出发的所有路径及其长度，从中找出最短路径。重复有哪些信誉好的足球投注网站，效率低。 方法二：初始时只看到一个源点。对顶点按广度优先扩展。随着图的扩展，发现更短路径时，图中顶点的的最短路径被更新（relax，松弛操作）。扩展时按照顶点编号的顺序效率低。 Dijkstra算法思想 按路径长度非递减的次序，逐步产生最短路径。 使用数组dist，dist[i]表示当前找到的源点v0到vi的最短路径长度。 把图中所有顶点分成两组，第一组：已求完最短路径的顶点；第二组：未求完最短路径的顶点。按最短路径长度递增的顺序逐个把第二组的顶点加到第一组。 初始时： S ={ }，dist[0]=0，dist[i]=+? 设S是已求得最短路径的顶点集合，则：下一条最短路径必然是从源点v0出发，中间只经过S中的顶点便可到达的那些顶点vx (vx?V-S )的路径中的一条。 每次求最短路径，就是在V-S中找具有最小dist值的顶点vk，将vk加入集合S，然后对vi?V-S，修改dist[i]值。 经第一次操作，S={v0}，若v0到vi有边，则dist[i]更新为边上的权值；v0到vi 无边，则dist[i]仍为+? 。 Dijkstra算法 ①设S为初始顶点, Ds=0且 ? i≠ S，有Di =＋∞ ②在未访问顶点中选择Dv最小的顶点v，访问v，令 S[v]=1。 ③依次考察v的邻接顶点w，若 Dv