最短路径算法课件_第1页
最短路径算法课件_第2页
最短路径算法课件_第3页
最短路径算法课件_第4页
最短路径算法课件_第5页
已阅读5页,还剩55页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

8.3单源最短路径

给定带权有向图G=(V,E),其中每条边的权是非负实数。另外,还给定V中的一个顶点,称为源。现在要计算从源到所有其它各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。 1、算法基本思想 Dijkstra算法是解单源最短路径问题的贪心算法。8.3单源最短路径 给定带权有向图G=(V,E),其中8.3单源最短路径

其基本思想是,设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。 初始时,S中仅含有源。设u是G的某一个顶点,把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径,并用数组dist记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u,将u添加到S中,同时对数组dist作必要的修改。一旦S包含了所有V中顶点,dist就记录了从源到所有其它顶点之间的最短路径长度。8.3单源最短路径 其基本思想是,设置顶点集合S并不断地8.3单源最短路径

例如,对右图中的有向图,应用Dijkstra算法计算从源顶点1到其它顶点间最短路径的过程列在下页的表中。8.3单源最短路径 例如,对右图中的有向图,应用Dijk8.3单源最短路径迭代Sudist[2]dist[3]dist[4]dist[5]初始{1}-10maxint301001{1,2}21060301002{1,2,4}4105030903{1,2,4,3}3105030604{1,2,4,3,5}510503060Dijkstra算法的迭代过程:

8.3单源最短路径迭代Sudist[2]dist[3]di

初始状态下,S中只有一个点(源点v1)。-11-111010∞3010010000s:distance:path:① 初始状态下,S中只有一个点(源点v1)。-11-1110

第二步,将S外距离S最近的点v2加入S。更新相应信息。-11-111010∞3010010000s:distance:path:1①②602 第二步,将S外距离S最近的点v2加入S。更新相应信息。-

第三步,将S外距离S最近的点v4加入S。更新相应信息。-11211010603010011000s:distance:path:1①②504④904 第三步,将S外距离S最近的点v4加入S。更新相应信息。-

第四步,将S外距离S最近的点v3加入S。更新相应信息。-1141401050309011010s:distance:path:1①②603④③ 第四步,将S外距离S最近的点v3加入S。更新相应信息。-

第五步,将S外距离S最近的点v5加入S。更新相应信息。-1141301050306011110s:distance:path:1①②④③⑤ 第五步,将S外距离S最近的点v5加入S。更新相应信息。-voidDijkstra(intG[][N],intv0,intdistance[],intpath[],intn)//源点v0到其他顶点的最短距离distance和最短路径下标path{int*s=newint[n];intminDis,i,j,u;

//初始化三个数组

voidDijkstra(intG[][N],int//逐次将各点加入S//在当前还未找到最短路径的顶点集中选取具有最短距离的顶点u//标记顶点u已从集合T加入到集合S中//修改从v0到其他顶点的最短距离和最短路径//逐次将各点加入SvoidDijkstra(intG[][N],intv0,intdistance[],intpath[],intn)//从源点v0到其他顶点的最短距离distance和最短路径下标path{int*s=newint[n];intminDis,i,j,u;

//初始化三个数组for(i=0;i<n;i++){voidDijkstra(intG[][N],intdistance[i]=G[v0][i];s[i]=0;if(I!=v0&&distance[i]<MAX)path[i]=v0;elsepath[i]=-1;}s[v0]=1;//标记顶点v0已从集合T加入到集合S中//在当前还未找到最短路径的顶点集中选取具有最短距离的顶点ufor(i=1;i<n;i++){minDis=MAX;for(j=0;j<=n;j++)distance[i]=G[v0][i];u到j有边相连,j才有可能因u的加入而距离源点更近if(s[j]==0&&distance[j]<minDis){u=j;minDis=distance[j];}s[u]=1;//标记顶点u已从集合T加入到集合S中//修改从v0到其他顶点的最短距离和最短路径for(j=0;j<n;j++)if(s[j]==0&&G[u][j]<MAX&&distance[u]+G[u][j]<distance[j])u到j有边相连,j才有可能因u的加入而距离源点更近if(s[distance[j]=distance[u]+G[u][j];path[j]=u;}}}distance[j]=distance[u]+G[u][j2、算法的正确性和计算复杂性(1)贪心选择性质(2)最优子结构性质(3)计算复杂性 对于具有n个顶点和e条边的带权有向图,如果用带权邻接矩阵表示这个图,那么Dijkstra算法的主循环体需要时间。这个循环需要执行n-1次,所以完成循环需要时间。算法的其余部分所需要时间不超过。2、算法的正确性和计算复杂性7.5所有点对的最短路径问题对于一个各边权值均大于0的有n个顶点的带权有向图G=(V,E),求所有顶点之间的最短路径和最短距离。图的邻接矩阵表示法123V=(b)(a)28196123L=

029061∞07.5所有点对的最短路径问题对于一个各边权值均大于0的有n个复习Dijkstra算法其基本思想是,设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。 初始时,S中仅含有源点。设u是G的某一个顶点,把从源点到u且中间只经过S中顶点的路称为从源到u的特殊路径,并用数组distance记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u,将u添加到S中,同时对数组distance作必要的修改。一旦S包含了所有V中顶点,distance就记录了从源到所有其它顶点之间的最短路径长度。复习Dijkstra算法其基本思想是,设置顶点集合算法中,我们不断更新以下三个数组:s数组:s[i],当顶点i加入S时,s[i]置1Distance数组:Distance[i]记录原点到顶点i的最短特殊路径长度。path数组:path[i]记录顶点i在其最短特殊路径上的前驱顶点。由该数组可求得原点到各点的最短路径。如:设源点是顶点1,path数组如下算法中,我们不断更新以下三个数组:

例如,对右图中的有向图,应用Dijkstra算法计算从源顶点1到其它顶点间最短路径的过程列在下页的表中。0141301050306011111s:distance:path:由源点1到顶点5的路径为:1->4->3->5 例如,对右图中的有向图,应用Dijkstra算法计算从源方法一:重复调用Dijkstra算法n次可轮流以每一个顶点为源点,重复调用狄克斯特拉算法函数Dijkstra()n次,即可求得所有顶点之间的最短路径和最短距离。利用Dijkstra()函数求所有顶点之间的最短路径算法如下。其中,distance[i][j]中存放着从顶点i到顶点j的最短距离,path[i][j]中存放着从顶点i到顶点j的最短路径的前一顶点下标。方法一:重复调用Dijkstra算法n次可轮流以每一个顶点为voidShortPath(AdjMWGraph&G,int**distance,int**path){Intn=G.NumOfVertices();for(inti=0;i<n;i++)Dijkstra(G,i,distance[i],path[i]);}由于狄克斯特拉算法的时间复杂度是O(n2),所以n次调用狄克斯特拉算法的时间复杂度是O(n3)。voidShortPath(AdjMWGraph&G,i该问题具有最优子结构性质例如上图中,若路线I和J是A到C的最优路径,则根据最优化原理,路线J必是从B到C的最优路线。该问题具有最优子结构性质例如上图中,若路线子问题的构造原问题:每个顶点到其他所有顶点的最短距离最小的子问题D0:从顶点i(不得经过任何其他顶点)到顶点j的距离;子问题D1:从顶点i(可以经过顶点1,不得经过其他任何其他顶点)到顶点j的距离。子问题的构造原问题:每个顶点到其他所有顶点的最短距离子问题Dk:从顶点i(可以经过顶点1、顶点2、……顶点k,不得经过任何其他顶点)到顶点j的距离。子问题Dn:从顶点i(可以经过顶点1、顶点2、……顶点n)到顶点j的距离。——即原问题子问题Dk:从顶点i(可以经过顶点1、顶点2、……顶点k,不递推关系的建立由di,jk-1推出di,jk的过程如下若k=0,di,jk=L[i][j](因为从i到j不允许经过任何其他顶点)若1≤k≤n,di,jk=min{di,jk-1,di,kk-1+dk,jk-1}子问题Dk-1:从顶点i(可以经过顶点1、顶点2、……、顶点k-1)到顶点j的距离。

子问题Dk:从顶点i(可以经过顶点1、顶点2、……顶点k-1、顶点k)到顶点j的距离。从子问题Dk-1:到子问题Dk,仅仅多考虑了一个顶点k。我们需要重新考虑从i到j的距离:

顶点i到顶点j,是不是从k走会更近?如果从顶点i到顶点j从顶点k走更近,则i到j的距离di,jk=i到k的距离di,kk-1

+

k到j的距离dk,jk-1如果顶点i到顶点j从顶点k走更远,甚至走不通,则保持原来的距离不变di,jk=di,jk-1

。由di,jk-1推出di,jk的过程,主要考虑的是顶点k的加入会引起什么变化?由不允许路过顶点k到允许路过顶点k,有些点间的距离是否会变的更近。递推关系的建立由di,jk-1推出di,jk的过程如下子例:考虑下图所示的带权有向图,求所有顶点之间的最短距离。V=(b)(a)12328196123L=

029061∞0计算过程例:考虑下图所示的带权有向图,求所有顶点之间的最短距离。V12328196029061∞0D0=029806130D1=028806130D2=028706130D3=Di,jk:从顶点i(可以经过顶点1、顶点2、……顶点k)到顶点j的距离。在D1中,第1行和第一列是不变的,因为说从顶点1到顶点j或顶点j到顶点1:允许经过顶点1是没有意义的D1[2][3]:从顶点2到顶点3的距离(可以经过顶点1)(1)不经过顶点1:仍是D0[2][3]=6;(2)过顶点1:D0[2][1]+D0[1][3]=8+9=17取最小值6D1[3][2]:从顶点3到顶点2的距离(可以经过顶点1)(1)不经过顶点1:仍是D0[3][2]=∞

;(2)过顶点1:D0[3][1]+D0[1][2]=1+2=3取最小值3D2[1][3]:从顶点1到顶点3的距离(也可以经过顶点2)(1)不经过顶点2:仍是D1[1][3]=9;(2)过顶点2:D1[1][2]+D1[2][3]=2+6=8取最小值812328196029D0=02算法设计重要发现:在从Dk-1到Dk的计算过程中中,第k行和第k列是不变的。(因为说从顶点k到顶点j或顶点j到顶点k允许经过顶点k是没有意义的)

而在从Dk-1到Dk的计算过程中也只用到第k行和第k列,也就是说,在这一步的计算过程中用到的数据都不会被覆盖。故在算法中仅使用一个矩阵D即可算法设计重要发现:在从Dk-1到Dk的计算过程中中,第k行和FLOYD算法FLOYD(int*L,intn){int*D=(int*)malloc((n+1)*(n+1)*sizeof(int));DL{将数组L复制到D};for(k=0;k<n;k++)for(i=0;i<n;i++)for(j=0;j<n;j++)D[i*n+j]=min(D[i*n+j],D[i*n+k]+D[k*n+j]);}FLOYD算法FLOYD(int*L,intn)8.3单源最短路径

给定带权有向图G=(V,E),其中每条边的权是非负实数。另外,还给定V中的一个顶点,称为源。现在要计算从源到所有其它各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。 1、算法基本思想 Dijkstra算法是解单源最短路径问题的贪心算法。8.3单源最短路径 给定带权有向图G=(V,E),其中8.3单源最短路径

其基本思想是,设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。 初始时,S中仅含有源。设u是G的某一个顶点,把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径,并用数组dist记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u,将u添加到S中,同时对数组dist作必要的修改。一旦S包含了所有V中顶点,dist就记录了从源到所有其它顶点之间的最短路径长度。8.3单源最短路径 其基本思想是,设置顶点集合S并不断地8.3单源最短路径

例如,对右图中的有向图,应用Dijkstra算法计算从源顶点1到其它顶点间最短路径的过程列在下页的表中。8.3单源最短路径 例如,对右图中的有向图,应用Dijk8.3单源最短路径迭代Sudist[2]dist[3]dist[4]dist[5]初始{1}-10maxint301001{1,2}21060301002{1,2,4}4105030903{1,2,4,3}3105030604{1,2,4,3,5}510503060Dijkstra算法的迭代过程:

8.3单源最短路径迭代Sudist[2]dist[3]di

初始状态下,S中只有一个点(源点v1)。-11-111010∞3010010000s:distance:path:① 初始状态下,S中只有一个点(源点v1)。-11-1110

第二步,将S外距离S最近的点v2加入S。更新相应信息。-11-111010∞3010010000s:distance:path:1①②602 第二步,将S外距离S最近的点v2加入S。更新相应信息。-

第三步,将S外距离S最近的点v4加入S。更新相应信息。-11211010603010011000s:distance:path:1①②504④904 第三步,将S外距离S最近的点v4加入S。更新相应信息。-

第四步,将S外距离S最近的点v3加入S。更新相应信息。-1141401050309011010s:distance:path:1①②603④③ 第四步,将S外距离S最近的点v3加入S。更新相应信息。-

第五步,将S外距离S最近的点v5加入S。更新相应信息。-1141301050306011110s:distance:path:1①②④③⑤ 第五步,将S外距离S最近的点v5加入S。更新相应信息。-voidDijkstra(intG[][N],intv0,intdistance[],intpath[],intn)//源点v0到其他顶点的最短距离distance和最短路径下标path{int*s=newint[n];intminDis,i,j,u;

//初始化三个数组

voidDijkstra(intG[][N],int//逐次将各点加入S//在当前还未找到最短路径的顶点集中选取具有最短距离的顶点u//标记顶点u已从集合T加入到集合S中//修改从v0到其他顶点的最短距离和最短路径//逐次将各点加入SvoidDijkstra(intG[][N],intv0,intdistance[],intpath[],intn)//从源点v0到其他顶点的最短距离distance和最短路径下标path{int*s=newint[n];intminDis,i,j,u;

//初始化三个数组for(i=0;i<n;i++){voidDijkstra(intG[][N],intdistance[i]=G[v0][i];s[i]=0;if(I!=v0&&distance[i]<MAX)path[i]=v0;elsepath[i]=-1;}s[v0]=1;//标记顶点v0已从集合T加入到集合S中//在当前还未找到最短路径的顶点集中选取具有最短距离的顶点ufor(i=1;i<n;i++){minDis=MAX;for(j=0;j<=n;j++)distance[i]=G[v0][i];u到j有边相连,j才有可能因u的加入而距离源点更近if(s[j]==0&&distance[j]<minDis){u=j;minDis=distance[j];}s[u]=1;//标记顶点u已从集合T加入到集合S中//修改从v0到其他顶点的最短距离和最短路径for(j=0;j<n;j++)if(s[j]==0&&G[u][j]<MAX&&distance[u]+G[u][j]<distance[j])u到j有边相连,j才有可能因u的加入而距离源点更近if(s[distance[j]=distance[u]+G[u][j];path[j]=u;}}}distance[j]=distance[u]+G[u][j2、算法的正确性和计算复杂性(1)贪心选择性质(2)最优子结构性质(3)计算复杂性 对于具有n个顶点和e条边的带权有向图,如果用带权邻接矩阵表示这个图,那么Dijkstra算法的主循环体需要时间。这个循环需要执行n-1次,所以完成循环需要时间。算法的其余部分所需要时间不超过。2、算法的正确性和计算复杂性7.5所有点对的最短路径问题对于一个各边权值均大于0的有n个顶点的带权有向图G=(V,E),求所有顶点之间的最短路径和最短距离。图的邻接矩阵表示法123V=(b)(a)28196123L=

029061∞07.5所有点对的最短路径问题对于一个各边权值均大于0的有n个复习Dijkstra算法其基本思想是,设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。 初始时,S中仅含有源点。设u是G的某一个顶点,把从源点到u且中间只经过S中顶点的路称为从源到u的特殊路径,并用数组distance记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u,将u添加到S中,同时对数组distance作必要的修改。一旦S包含了所有V中顶点,distance就记录了从源到所有其它顶点之间的最短路径长度。复习Dijkstra算法其基本思想是,设置顶点集合算法中,我们不断更新以下三个数组:s数组:s[i],当顶点i加入S时,s[i]置1Distance数组:Distance[i]记录原点到顶点i的最短特殊路径长度。path数组:path[i]记录顶点i在其最短特殊路径上的前驱顶点。由该数组可求得原点到各点的最短路径。如:设源点是顶点1,path数组如下算法中,我们不断更新以下三个数组:

例如,对右图中的有向图,应用Dijkstra算法计算从源顶点1到其它顶点间最短路径的过程列在下页的表中。0141301050306011111s:distance:path:由源点1到顶点5的路径为:1->4->3->5 例如,对右图中的有向图,应用Dijkstra算法计算从源方法一:重复调用Dijkstra算法n次可轮流以每一个顶点为源点,重复调用狄克斯特拉算法函数Dijkstra()n次,即可求得所有顶点之间的最短路径和最短距离。利用Dijkstra()函数求所有顶点之间的最短路径算法如下。其中,distance[i][j]中存放着从顶点i到顶点j的最短距离,path[i][j]中存放着从顶点i到顶点j的最短路径的前一顶点下标。方法一:重复调用Dijkstra算法n次可轮流以每一个顶点为voidShortPath(AdjMWGraph&G,int**distance,int**path){Intn=G.NumOfVertices();for(inti=0;i<n;i++)Dijkstra(G,i,distance[i],path[i]);}由于狄克斯特拉算法的时间复杂度是O(n2),所以n次调用狄克斯特拉算法的时间复杂度是O(n3)。voidShortPath(AdjMWGraph&G,i该问题具有最优子结构性质例如上图中,若路线I和J是A到C的最优路径,则根据最优化原理,路线J必是从B到C的最优路线。该问题具有最优子结构性质例如上图中,若路线子问题的构造原问题:每个顶点到其他所有顶点的最短距离最小的子问题D0:从顶点i(不得经过任何其他顶点)到顶点j的距离;子问题D1:从顶点i(可以经过顶点1,不得经过其他任何其他顶点)到顶点j的距离。子问题的构造原问题:每个顶点到其他所有顶点的最短距离子问题Dk:从顶点i(可以经过顶点1、顶点2、……顶点k,不得经过任何其他顶点)到顶点j的距离。子问题Dn:从顶点i(可以经过顶点1、顶点2、……顶点n)到顶点j的距离。——即原问题子问题Dk:从顶点i(可以经过顶点1、顶点2、……顶点k,不递推关系的建立由di,jk-1推出di,jk的过程如下若k=0,di,jk=L[i][j](因为从i到j不允许经过任何其他顶点)若1≤k≤n,di,jk=min{di,jk-1,di,kk-1+dk,jk-1}子问题Dk-1:从顶点i(可以经过顶点1、顶点2、……、顶点k-1)到顶点j的距离。

子问题Dk:从顶点i(可以经过顶点1、顶点2、……顶点k-1、顶点k)到顶点j的距离。从子问题Dk-1:到子问题Dk,仅仅多考虑了一个顶点k。我们需要重新考虑从i到j的距离:

顶点i到顶点j,是不是从k走会更近?如果从顶点i到顶点j从顶点k走更近,则i到j的距离di,jk=i到k的距离di,kk-1

+

k到j的距离dk,jk-1如果顶点i到顶点j从顶点k走更远,甚至走不通,则保持原来的距离不变di,jk=di,jk-1

。由di,jk-1推出di,jk的过程,主要考虑的是顶点k的加入会引起什么变化?由不允许路过顶点k到

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论