数据结构-最短路一

第五章最短路吉林大学计算机学院谷方明fmgu2002@问题背景最短路是实际应用中最常遇到的任务。旅游：长春杭州，路程、时间、费用最短路问题：在给定的图中，从某顶点出发，找从该点到其它顶点cost最小的路径。路径的cost指该路径边的权值累加和。最短路问题分类两个顶点间的最短路：从一个指定的顶点到达另一指定顶点的最短路问题。单源最短路(SingleSourceShortestPath,SSSP)：从一个指定的顶点到其它所有顶点的最短路径问题。任意顶点间的最短路：所有顶点间的最短路；13258102045301202341.无权图的单源最短路无权——相当于所有边的权值都为1.源点到各顶点的路径长度：所经历的边的数目思想：从源点开始由近及远依次求各顶点的最短路径设Di为源点S到顶点i的最短路径长度①访问初始顶点S，即令DS=0。②从S出发，找最短路径为1的顶点，即S的所有邻接顶点w，令Dw=DS+1③从上步访问的顶点w出发，找最短路径为2的顶点，即w未被访问的邻接顶点v，令Dv=Dw+1④继续上述过程，直至处理完所有顶点。1V12V63V51V32V43V20SV0算法思想上述过程中，访问顶点的次序与对图进行广度优先遍历的次序是一致的;1V12V63V51V32V43V20SV0算法实现图采用邻接表存储；用队列保存待处理顶点；使用数组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中其它顶点的最短路径。要求各边的权值为非负实数。无权最短路算法？v0v1v2283分析方法一：枚举从源点出发的所有路径及其长度，从中找出最短路径。重复搜索，效率低。方法二：初始时只看到一个源点。对顶点按广度优先扩展。随着图的扩展，发现更短路径时，图中顶点的的最短路径被更新（relax，松弛操作）。扩展时按照顶点编号的顺序效率低。1325405041020Dijkstra算法思想按路径长度非递减的次序，逐步产生最短路径。使用数组dist，dist[i]表示当前找到的源点v0到vi的最短路径长度。把图中所有顶点分成两组，第一组：已求完最短路径的顶点；第二组：未求完最短路径的顶点。按最短路径长度递增的顺序逐个把第二组的顶点加到第一组。初始时：S={}，dist[0]=0，dist[i]=+

设S是已求得最短路径的顶点集合，则：下一条最短路径必然是从源点v0出发，中间只经过S中的顶点便可到达的那些顶点vx(vxV-S)的路径中的一条。每次求最短路径，就是在V-S中找具有最小dist值的顶点vk，将vk加入集合S，然后对viV-S，修改dist[i]值。经第一次操作，S={v0}，若v0到vi有边，则dist[i]更新为边上的权值；v0到vi无边，则dist[i]仍为+

。S

V-SDijkstra算法①设S为初始顶点,Ds=0且

i≠S，有Di=＋∞②在未访问顶点中选择Dv最小的顶点v，访问v，令S[v]=1。③依次考察v的邻接顶点w，若

Dv+weight(<v,w>)<Dw

，则改变Dw的值，使Dw=

Dv+weight(<v,w>)。④重复②③，直至所有顶点被访问。01234024310∧5134∧3038∧225410∧02024412∧例1325810204530120234spathdist0000003421∞∞∞

0∞1325810204530120234spathdist0000003421∞∞3

030v0v0013302343∞∞325813300234302811spathdist000000342128113

030v0v0v1v11325810204530120234312041581323423111325810204530120234spathdist000000342115113

023v0v3V3V1120415813234231131325810204530120234spathdist000000342115113

023v0v3V3V1120415813234231131325810204530120234spathdist000000342115113

023v0v3V3V1定理5.4Dijkstra算法可以按照非递减次序依次得到各顶点的最小路径长度。证明：归纳法算法得到的路径值是各顶点的最小路径长度。算法得到的路径值是按非递减次序得到的。svud>0v0v1v243-2Dijkstra算法描述算法DShortestPath(v)/*计算v到其他各顶点的最短路径*/D1[初始化]

for(i=1;i<=n;i++){ path[i]=-1;dist[i]=max;s[i]=0;//数组s[i]记录i是否已计算完}dist[v]=0;D2[求从v到其他各顶点的最短路径]for(j=1;j<n;j++){ldist=max;//循环:确定即将被访问的顶点u

for(i=1;i<=n;i++) if(dist[i]<ldist&&s[i]==0) {ldist=dist[i];u=i;}s[u]=1. for(p=Head[u].adjacent;p;p=p->link){ k=p->VerAdj;

if(dist[u]+cost(p)<dist[k])//松弛{dist[k]dist[u]+cost(p);path[k]=u;}}}算法分析时间复杂性：在Dijkstra算法中，循环扫描被访问顶点的边链表，时间复杂性为O(du)（du为顶点u的邻接顶点个数）；循环扫描顶点表求最小dist，时间复杂性为O(n)；循环体要被执行n次，因此整个算法的时间复杂性为与存储方式无关；与边数无关3.每对顶点间的最短路径已知一个带权有向图，对每一对顶点vi

vj，求vi

与vj间的最短路径和最短路径长度。如果是正权图，可依次把每个顶点作为源点，执行n次Dijkstra算法。Floyd算法设图是用邻接矩阵存储的权图。求顶点到顶点的最短路径的基本思想是：如果，则说明至存在弧，将该弧设为当前最短路径，但该路径未必是最终最短路径，我们需要进行n次试探。设顶点集，，…，.第一步：考察是否存在路径，其经由顶点所构成的集合是的子集S0（即弧<Vi,V0>和<V0,Vj>是否存在）。若存在，比较该路径与当前最短路径的长度值，取值较小的路径作为新的当前最短路径，它是Vi至Vj的经由顶点序列号小于1的最短路径。第二步：考察是否存在路径，其经由顶点所构成的集合是S1的子集，但不是S0的子集。若存在，比较该路径与当前最短路径的长度值，取值较小的路径作为新的当前最短路径，它是Vi至Vj的经由顶点序列号小于2的最短路径。……第n步：考察是否存在路径，其经由顶点所构成的集合是Sn-1的子集，但不是Sn-2的子集。若存在，比较该路径与当前最短路径的长度值，取值较小的路径作为新的当前最短路径，它是Vi至Vj的经由顶点序列号小于的最短路径。算法实现设邻接矩阵存储图，edge[n][n]为图的邻接矩阵；定义一个n阶方阵序列：A(-1),A(0),…,A(n-1).定义初始矩阵A(-1)[i][j]=Edge[i][j]；1求A(0),即从vi到vj经由顶点可以是{v0}的最短路径；2求A(1),即从vi到vj经由顶点可以是{v0,v1}的最短路径；

…n求A(n-1),即从vi到vj经由顶点可以是{v0,

v1,…,vn-1}的最短路径长度；其中A(k)[i][j]=min{A(k-1)[i][j]，

A(k-1)[i][k]+A(k-1)[k][j]},k=0,1,…,n-1Path(1)Path(0)Path(1)Path(2)Path(3)01230123012301230123010101010101110111031111111111111121112131222122010201120112011311311131113122312031A(1)A(0)A(1)A(2)A(3)01230123012301230123001401401103011030193109209209212092110822350834073406340634063606060910609106023013685941201409235086010230123从A(3)知，顶点1到0的最短路径长度为a[1][0]=11，其最短路径：path[1][0]=2，表示顶点2顶点0；

path[1][2]=3，表示顶点3顶点2；path[1][3]=1，表示顶点1顶点3；从顶点1到顶点0最短路径为：<1,3>，<3,2>，<2,0>（见Path(3)中第1行，第0、2、3列)

算法描述算法Floyd()/*求每对顶点间的最短路径，其中edge[n][n]表示有n个顶点的图的邻接矩阵；A[i][j]表示顶点Vi至Vj的最短路径长度；path[i][j]表示相应路径上顶点j的前一个顶点的序号*/F1[