最短路径问题课件

20最短路径最短路径问题关键路径复习从某个源点到其余各点的最短路径每一对顶点之间的最短路径小结和作业20最短路径关键路径1、求出拓扑排序序列2、ve(0)=0ve(j)=max(ve(i)+dut(i,j))

<i,j>∈T,T是以j为头的弧的集合3、求出逆拓扑排序序列4、vl(n-1)=ve(n–1)v(i)=min(vl(j)-dut(i,j))

<i,j>∈T,T是以j为头的弧的集合20最短路径关键路径5、对每个活动ai，对应的弧是<j,k>

e(i)=ve(j)l(i)=vl(k)–dut(j,k)

6、对每个活动ai

，如果，e(i)=l(i)，输出ai，ai是关键活动20最短路径关键路径A练习：求下图各活动弧ai的e(ai)和l(ai)，个事件vj的ve(vj)和vl(vj)，列出各关键路径。BCDEFGHWXa1=1a2=6a3=3a4=4a5=2a6=7a7=5a8=10a9=6a10=11a11=8a12=21a13=16a14=9a15=17a16=13a17=1220最短路径关键路径算法StatusToplogicalOrder(ALGraghG,Stack&T,SqList&ve){ InitStack(S);InitStack(T);count=0;ve[0..G.vexnum-1]=0;FindInDegree(G,indegree); for(i=0;i<G.vexnum;i++){if(!indegree[i])push(S,i);}

while(!EmptyStack(S)){

…………}//while if(count<G.vexnum)returnERROR; elsereturnOK;}20最短路径关键路径算法while(!EmptyStack(S)){Pop(S,v);Push(T,v);++count;for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w)){ if(--indegree(w)==0)Push(S,w);//入度-1为0，则入栈

if(ve[v]+<v,w>>ve[w])ve[w]=ve[v]+<v,w>//计算ve}//for}//while

20最短路径关键路径算法StatusCriticalPath(ALGraghG){//逆邻接表

if(!ToplogicalOrder(G,T,ve))returnERROR;

vl[0..G.vexnum-1]=ve[0..G.vexnum-1];//用ve初始化vl

while(!stackEmpty(T)){

pop(T,v);

//计算vlfor(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w)){ if(vl[v]-<w,v><vl[w])vl[w]=vl[v]-<w,v>;

}//for

}//while

…………}//endofCriticalPath20最短路径关键路径算法

for(j=0;j<G.vexnum;++j)

for(p=G.vertices[j].firstarc;p;p=p->nextarc){

k=p->adjvex;dut=*(p->info);

ee=ve[k];el=vl[j]-dut;//活动的时间

tag=(ee=el)?’*’:’’;

printf(j,k,dut,ee,el,tag);

}//endoffor(p)20最短路径关键路径算法分析1.求关键路径的总的时间复杂度：O(n+e)2.AOE-网求出的路径可能大于一条。这种情况下只有同时提高所有关键路径上的活动的速度，才能使整个工期缩短。20最短路径单源点的最短路径V01001010550V1V2V5V460V32030给定带权有向图G和V0，求从V0到其余各顶点的最短路径。20最短路径Dijkstra算法按照路径长度递增的次序产生最短路径源点v1…v220最短路径终点一定是V0的邻接点Vj，边一定是<V0,Vj>，它在V0的所有邻接边中最短。该路径是V0Vj1、长度最短的路径V01001010550V1V2V5V460V32030Dijkstra算法20最短路径如果路径V0Vj

不是最短路径，则一定有另外一条路径，V0W…U,它比V0Vj短。但是，因为W是V0的邻接点，所以，边<V0,W>一定比边<V0,Vj>长。所以，不存在比V0Vj更短的路径。不失一般性，假设j=1Dijkstra算法20最短路径它只可能有两种情况:

1）直接从源点到该点,V0X2）从源点经过顶点v1，再到达该顶点,V0V1X假设存在另外一个路径，V0WX，它比上面的路径更短。如果W≠V1，则V0W比V0WX更短，所以，要选取W，符合形式一如果W=V1，则符合形式二Dijkstra算法2、下一条路径长度次短的最短路径的特点:20最短路径3、用S表示已经选取的顶点集合

S={V0,V1,V2,…Vj}下次要选取的顶点X，从V0到X的路径中经过的顶点一定都在S中。假设存在路径V0→→W→X，WS，该路径最短。因为路径V0→→W→X比路径V0→→W长，所以会选择W，而V0到W的路径中的顶点都在S中。Dijkstra算法20最短路径V01001010550V1V2V5V460V32030S={V0}S={V0,V2}S={V0,V2,V4}S={V0,V2,V4,V3}S={V0,V2,V4,V3,V5}V2V5V4V3Dijkstra算法20最短路径为了减少计算量设置辅助数组D，其中每个分量D[k]

表示当前所求得的从源点到顶点k

的最短路径。初始时

D[k]=<源点到顶点k的弧上的权值>当S=S∪{Vj}D[K]=min(D[k],D[Vj]+<Vj,K>)Dijkstra算法20最短路径abcdefg15210765910444终点bcdefgD路径15ab2ac10ad2

9ace6acf6

169

10

1414

acfgadgDijkstra算法20最短路径如何保存V0到V的路径？1、保存V0到V的路径上的顶点（即：不保存边和顶点之间的顺序）2、存储结构：n×n的矩阵pDijkstra算法3、矩阵的第V行表示V0到V的路径上顶点如果顶点W在路径上，则p[v][w]=TRUE否则，p[v][w]=FALSE20最短路径初始：如果V与顶点V0邻接，则p[v][V0]=TRUE，其它数矩阵元素的值都是FALSE。当从V0到V的路径是经过V0到W的路径，然后，通过边<W,V>到达V，则p[v]=p[w]，p[v][v]=TRUEDijkstra算法20最短路径Dijkstra算法V01001010550V1V2V5V460V32030F

FFFFFV0V1V2V3V4V5V0V1V2V3V4V5FFFFFF

TFTFFF

FFFFFF

TFFFTF

TFFFFT选取V2后，V0到V3的路径经过V2P[V3]=P[V2]P[V3][V3]=TRUE

TFTFFF

TFT

TFF20最短路径Dijkstra算法描述1）在所有从源点出发的弧中选取一条权值最小的弧，即为第一条最短路径。2）修改其它各顶点的D[k]值。假设求得最短路径的顶点为u，若D[u]+G.arcs[u][k]<D[k]则将D[k]=D[u]+G.arcs[u][k]V0和k之间存在弧V0和k之间不存在弧Dijkstra算法20最短路径Dijkstra算法实现图：带权的邻接矩阵

路径：矩阵距离：数组DS中的集合：数组final[]，如果final[v]=TRUE，则v在S中20最短路径voidShortestPath_DIJ(MGraphG,intv0,PathMatrix&P, ShortestPathTable&D){

for(v=0;v<G.vexnum;++v){

final[v]=FALSE;//S中的顶点

D[v]=G.arcs[v0][v];//V0到v的路径的长度

for(w=0;w<G.vexnum;++w)

p[v][w]=FALSE;

if(D[v]<INFINITY){//V0的邻接点

p[v][v0]=TRUE;

p[v][v]=TRUE; }//if }//for

final[v0]=TRUE;

…………}Dijkstra算法实现20最短路径voidShortestPath_DIJ(MGraphG,intv0,PathMatrix&P, ShortestPathTable&D){

//主循环，每次求得v0到某个顶点v的最短路径，

//并将v加到S集中

for(i=1;i<G.vexnum;++i){

min=INFINITY;//找余下顶点中的最短路径

for(w=0;w<G.vexnum;++w){ if(!final[w])

if(D[w]<min){v=w;min=D[w];}

final[v]=TRUE;//v入选，即v0到v的路径最短

…………}}Dijkstra算法实现20最短路径voidShortestPath_DIJ(MGraphG,intv0,PathMatrix&P, ShortestPathTable&D){

for(w=0;w<G.vexnum;++w) {

if(!final[w]&&(min+G.arcs[v][w]<D[w])){

D[w]=min+G.arcs[v][w];//修改距离

p[w]=p[v];//修改路径

p[w][w]=TRUE; }//endofif }//endoffor}//voidDijkstra算法实现20最短路径课堂练习123456787810152030601015163366求出从顶点1到其它定点的最短路径。要求写出final、D、和p的变化过程。20最短路径Dijkstra算法讨论2、权值要为正数，否则，得不到正确结果1、算法的总的时间复杂度：O(n2)3、当权值出现负数时，要使用Bellman-Ford算法20最短路径Dijkstra算法讨论都是从一个顶点开始都有一个距离数组D都有一个顶点是否已经被选取的标志4、和Prim算法有相似和不同的地方20最短路径abcdegf195141827168213127abegf14d8c351621Prim算法产生的最小生成树Dijkstra算法讨论20最短路径abcdegf195141827168213127abegf14d8c51821Dijkstra算法产生的支撑树19Dijkstra算法讨论20最短路径每一对顶点之间的最短路径v0v2v1326411cab问题：给定一个图G，求出G中任意两个顶点之间的最短路径（距离和经过的顶点）解决方法：对图中的每个结点V，以V为源点，调用Dijkstra算法时间复杂度为O(n3)20最短路径首先假设顶点vi和vj之间的最短路径是通过连接vi到j的弧，然后不断的调整它从vi

到vj的所有可能存在的路径中，选出一条长度最短的路径弗洛伊德算法的基本思想是动态规划Floyd

算法20最短路径考察从Vi到Vj且中间顶点属于集合{V1,V2,...Vk}的所有路径，设其中最短的一条路径为P。Floyd

算法若Vk不是路径P的中间节点，则P的所有中间顶点都属于集合{V1,V2,..Vk-1};因此从Vi到Vj且中间顶点属于集合{V1,V2,...Vk-1}的最短路径也是从Vi到Vj且中间顶点属于集合{V1,V2,...Vk}的最短路径；20最短路径Floyd

算法若Vk是P的中间节点，我们把P分解成P1={Vi,...Vk}和P2={Vk,..,Vj}，显然P1是从Vi到Vk的一条最短路径且满足所有的中间顶点均属于集合{V1,V2,..Vk-1};P2是从Vk到Vj的一条最短路径且满足所有的中间顶点均属于集合{V1,V2,..Vk-1};20最短路径Floyd

算法对任一对顶点Vi和Vj求Vi和Vj之间经过中间顶点集合{V1}的最短路径再求Vi和Vj之间经过中间顶点集合{V1，V2}的最短路径设P1是Vi到V2，且中间顶点集合是{V1}的最短路径设P2是V2到Vj，且中间顶点集合是{V1}的最短路径如果P1+P2<P(Vi,Vj)，则P1+P2是Vi到Vj的最短路径，经过的中间顶点是{V1,V2}20最短路径Floyd

算法直到求出顶点Vi和Vj之间经过{V1,V2,…,Vn}的最短路径20最短路径Floyd

算法1.定义一个n阶方阵D(-1)，表示初始时，任意两个顶点(i,j)之间的距离

D(-1)[i][j]=G.arcs[i][j]

由D(k-1)生成新的矩阵D(k),表示任意连个顶点之间最短路径的长度，中间经过的顶点的编号小于K。

D(k)=Min(D(k-1)[i][j],D(k-1)[i][k]+D(k-1)[k][j]2.fork=0ton-13.D(n)中存放的是任意两个顶点之间的最短路径20最短路径0121200403∞121200D-1v0v2v1326411cab116200ab0caacbabc0P-1Floyd

算法演示20最短路径121200v0v2v1326411cab0121200403∞116200ab0caacbabc0437cabD0P0Floyd

算法演示20最短路径11121200v0v2v1326411cab0121200066200ab0caacbabc0437cab24abcD1P1Floyd

算法演示20最短路径6121200v0v2v1326411cab012120006200ab0caacbabc0437cababc235bcaD2P2Floyd

算法演示20最短路径采用邻接矩阵存储每对顶点之间的路径长度采用三维数组存储每对顶点之间经过的顶点Floyd

算法实现20最短路径voidshortestPath_FLOYD(MGraphG,PathMatrix&P[], DistancMatrix&D){

for(v=0;v<G.vexnum;++v)//各对顶点初始已知路径和距离

for(w=0;w<G.vexnum;++w){

D[v][w]=G.arcs[v][w];//D-1

for(u=0;u<G.vexnum;++u)P[v][w][u]=FALSE;

if(D[v][w]<INFINITY){//从v到w有直接路径

P[v][w][v]=TRUE;//P-1

P[v][w][w]=TRUE;

}//if

}//for

…………

}Floyd

算法实现20最短路径voidshortestPath_FLOYD(MGraphG,PathMatrix&P[], DistancMatrix&D){

…………

for(u=0;u<G.vexnum;++u)//中间结点 for(v=0;v<G.vexnum;++v){

for(w=0;w<G.vexnum;++w)

if(D[v][u]+D[u][w]<D[v][w]){

//从v经u到w的一条路径更短

D[v][w]=D[v][u]+D[u][w];

for(i=0;i<G.vexnum;i++)