数据结构-最短路径课件

专题3：最短路径123最短路径的定义Dijkstra算法Floyd算法专题3：最短路径123最短路径的定义Dijkstra算法1在非网图中，最短路径是指两顶点之间经历的边数最少的路径。

6.4最短路径最短路径

BAEDCAE：1ADE：2ADCE：3ABCE：3在非网图中，最短路径是指两顶点之间经历的边数最少的路径。62最短路径

在网图中，最短路径是指两顶点之间经历的边上权值之和最短的路径。

BAEDC105030101002060AE：100ADE：90ADCE：60ABCE：706.4最短路径最短路径在网图中，最短路径是指两顶点之间经历的边上权值之和3问题描述：给定带权有向图G＝(V,E)和源点v∈V，求从v到G中其余各顶点的最短路径。

单源点最短路径问题

应用实例——计算机网络传输的问题：怎样找到一种最经济的方式，从一台计算机向网上所有其它计算机发送一条消息。迪杰斯特拉（Dijkstra）提出了一个按路径长度递增的次序产生最短路径的算法——Dijkstra算法。6.4最短路径问题描述：给定带权有向图G＝(V,E)和源点v∈V，求从v4基本思想：设置一个集合S存放已经找到最短路径的顶点，S的初始状态只包含源点v，对vi∈V-S，假设从源点v到vi的有向边为最短路径。以后每求得一条最短路径v,…,vk，就将vk加入集合S中，并将路径v,…,vk,vi与原来的假设相比较，取路径长度较小者为最短路径。重复上述过程，直到集合V中全部顶点加入到集合S中。Dijkstra算法6.4最短路径集合

V-S集合

Svkvvi基本思想：设置一个集合S存放已经找到最短路径的顶点，S的初始5Dijkstra算法——伪代码6.4最短路径设源点v，w<v,vj>表示从顶点v到顶点vj的权值，dist(v,vj)表示从顶点v到顶点vj的最短路径长度，Dijkstra算法的基本思想用伪代码描述如下：1.初始化：集合S={v}；dist(v,vj)=w<v,vj>,(j=1..n)；2.重复下述操作直到S==V2.1dist(v,vk)=min{dist(v,vj),(j=1..n)}；

2.2S=S+{vk}；

2.3dist(v,vj)=min{dist(v,vj),dist(v,vk)+w<vk,vj>}；Dijkstra算法——伪代码6.4最短路径设源点v，w6ABAEDC105030101002060S={A}A→B:(A,B)10A→C:(A,C)∞A→D:(A,D)30A→E:(A,E)100Dijkstra算法6.4最短路径ABAEDC105030101002060S={A}Dijk7ABAEDC105030101002060S={A,B}A→B:(A,B)10A→C:(A,B,C)60A→D:(A,D)30A→E:(A,E)100BDijkstra算法6.4最短路径ABAEDC105030101002060S={A,B}B8ABAEDC105030101002060S={A,B,D}A→B:(A,B)10A→C:(A,D,C)50A→D:(A,D)30A→E:(A,D,E)90BDDijkstra算法6.4最短路径ABAEDC105030101002060S={A,B,9ABAEDC105030101002060S={A,B,D,C}A→B:(A,B)10A→C:(A,D,C)50A→D:(A,D)30A→E:(A,D,C,E)60BDCDijkstra算法6.4最短路径ABAEDC105030101002060S={A,B,10ABAEDC105030101002060Dijkstra算法S={A,B,D,C,E}A→B:(A,B)10A→C:(A,D,C)50A→D:(A,D)30A→E:(A,D,C,E)60BDCE6.4最短路径ABAEDC105030101002060Dijkstra算11图的存储结构：带权的邻接矩阵存储结构

数组dist[n]：每个分量dist[i]表示当前所找到的从始点v到终点vi的最短路径的长度。初态为：若从v到vi有弧，则dist[i]为弧上权值；否则置dist[i]为∞。数组s[n]：存放源点和已经生成的终点，其初态为只有一个源点v。

数据结构

:6.4最短路径图的存储结构：带权的邻接矩阵存储结构数组dist[n]：121.初始化数组dist和s；2.while(s中的元素个数<n)2.1在dist[n]中求最小值，其下标为k；

2.2输出dist[k]；

2.3修改数组dist；

2.4将顶点vk添加到数组s中；Dijkstra算法——伪代码6.4最短路径1.初始化数组dist和s；Dijkstra算法——伪代码13Dijkstra算法——伪代码6.4最短路径ABEDC105030101002060Dijkstra算法——伪代码6.4最短路径ABEDC114Dijkstra算法——C++描述6.4最短路径voidDijkstra(MGraphG,intv){for(i=0;i<G.vertexNum;i++)//初始化数组dist[n]dist[i]=G.arc[v][i];s[0]=v;dist[v]=0;//初始化集合S，标记顶点v为源点num=1;while(num<G.vertexNum)//当顶点数num小于图的顶点数{for(k=0,i=0;i<G.vertexNum;i++)//在dist中查找最小值元素

if((dist[i]!=0)&&(dist[i]<dist[k]))k=i;cout<<dist[k];s[num++]=k;//将新生成的终点加入集合Sdist[k]=0;//置顶点k为已生成终点标记

for(i=0;i<G.vertexNum;i++)//修改数组distif(dist[i]>dist[k]+G.arc[k][i])dist[i]=dist[k]+G.arc[k][i];}}Dijkstra算法——C++描述6.4最短路径void15Dijkstra算法——C++描述6.4最短路径voidDijkstra(MGraphG,intv){for(i=0;i<G.vertexNum;i++)dist[i]=G.arc[v][i];s[0]=v;dist[v]=0;num=1;while(num<G.vertexNum){for(k=0,i=0;i<G.vertexNum;i++)

if((dist[i]!=0)&&(dist[i]<dist[k]))k=i;cout<<dist[k];s[num++]=k;dist[k]=0;

for(i=0;i<G.vertexNum;i++)if(dist[i]>dist[k]+G.arc[k][i])dist[i]=dist[k]+G.arc[k][i];}}时间复杂度？O(n)O(n)O(n)O(n)因此，时间复杂度是O(n2)。Dijkstra算法——C++描述6.4最短路径void166.4最短路径数组path[n]：path[i]是一个字符串，表示当前所找到的从始点v到终点vi的最短路径。初态为：若从v到vi有弧，则path[i]为vvi；否则置path[i]空串。每次迭代依据下式进行修改：如何修改存储结构，使得在求得最短路径长度的同时求得最短路径？if(dist[i]>dist[k]+G.arc[k][i])path[i]=path[k]+G.vertex[i]Dijkstra算法——C++描述6.4最短路径数组path[n]：path[i]是一个字17每一对顶点之间的最短路径

问题描述：给定带权有向图G＝(V,E)，对任意顶点vi,vj∈V（i≠j），求顶点vi到顶点vj的最短路径。

解决办法1：每次以一个顶点为源点调用Dijkstra算法。显然，时间复杂度为O(n3)。解决办法2：弗洛伊德提出的求每一对顶点之间的最短路径算法——Floyd算法，其时间复杂度也是O(n3)，但形式上要简单些。6.4最短路径每一对顶点之间的最短路径问题描述：给定带权有向图G＝(V,18基本思想：对于从vi到vj的弧，进行n次试探：首先考虑路径vi,v0,vj是否存在，如果存在，则比较vi,vj和vi,v0,vj的路径长度，取较短者为从vi到vj的中间顶点的序号不大于0的最短路径。在路径上再增加一个顶点v1，依此类推，在经过n次比较后，最后求得的必是从顶点vi到顶点vj的最短路径。

Floyd算法6.4最短路径基本思想：对于从vi到vj的弧，进行n次试探：首先考虑路径v1904116023∞0有向网图邻接矩阵Floyd算法acb3461126.4最短路径0411有向网图20Floyd算法acb346112dist-1

=04116023∞0path-1

=

abacbabcca初始化6.4最短路径Floyd算法acb346112dist-1=0421Floyd算法acb346112dist-1

=04116023∞0path-1

=

abacbabcca第1次迭代dist0

=0411602370path0

=

abacbabccacab

6.4最短路径Floyd算法acb346112dist-1=0422Floyd算法acb346112第2次迭代dist0

=0411602370path0

=

abacbabccacabdist1

=046602370path1

=

ababc

babccacab6.4最短路径Floyd算法acb346112第2次迭代dist0=023Floyd算法acb346112第3次迭代dist2

=046502370path2

=

ababcbcabccacabdist1

=046602370path1

=

ababcbabccacab6.4最短路径Floyd算法acb346112第3次迭代dist2=024图的存储结构：带权的邻接矩阵存储结构

数组dist[n][n]：存放在迭代过程中求得的最短路径长度。迭代公式：数组path[n][n]：存放从vi到vj的最短路径，初始为path[i][j]="vivj"。数据结构dist-1[i][j]=arc[i][j]dist

k[i][j]=min{distk-1[i][j],distk-1[i][k]+distk-1[k][j]}