数据结构-从概念到C++实现（第4版）课件 5-5最短路径

5-5最短路径v第五章图最短路径的定义最短路径：非带权图——边数最少的路径v0到v4的最短路径：v0v4：1v0v3v4：2v0v1v2v4：3v0v3v2v4：3v0v2v3v4v1最短路径：带权图——边上的权值之和最少的路径101003050201060v0到v4的最短路径：v0v4：100v0v3v4：90v0v1v2v4：70v0v3v2v4：60v0v2v3v4v1对于非带权图，如何求最短路径？广度优先遍历v0v1v4v0v1广度优先遍历序列：level=01101003050201060对于带权图，如何求最短路径？最短路径的定义Dijkstra算法Floyd算法学什么？5-5-1Dijkstra算法v第五章图单源点最短路径问题【问题】给定带权有向图G＝(V,E)和源点v∈V，求从v到G中其余各顶点的最短路径

【想法】。。。。。。【算法】Dijstra算法应用实例——计算机网络传输的问题：怎样找到一种最经济的方式，从一台计算机向网上所有其它计算机发送一条消息v0v2v3v4v1101003050201060基本思想v：源点S：已经生成最短路径的终点w<v,vi>：从顶点v到顶点vi

的权值dist(v,vi)：表示从顶点v

到顶点vi

的最短路径长度算法：Dijkstra算法输入：有向网图

G=(V，E)，源点

v

输出：从

v到其他所有顶点的最短路径1.初始化：集合S={v}；dist(v,vi)=w<v,vi>,(i=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>}；vivS

V-Svk当前生长点算法：Dijkstra算法输入：有向网图

G=(V，E)，源点

v

输出：从

v到其他所有顶点的最短路径1.初始化：集合S={v}；dist(v,vi)=w<v,vi>,(i=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算法输入：有向网图

G=(V，E)，源点

v

输出：从

v到其他所有顶点的最短路径1.初始化：集合S={v}；dist(v,vi)=w<v,vi>,(i=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>}；如何存储dist(v,vi)呢？

待定路径表（当前的最短路径）

整型数组dist[n]：存储当前最短路径的长度

字符串数组path[n]：存储当前的最短路径，即顶点序列存储结构v0v2v3v4v1101003050201060当前的最短路径：<v0,v1>10<v0,v2>∞<v0,v3>30<v0,v4>100v0v2v3v4v11010030∞010∞30100dist[n]

运行实例v0v2v3v4v1101003050201060当前的最短路径：<v0,v1,v2>60<v0,v3>30<v0,v4>100v0v2v3v4v11010030∞50010∞30100dist[n]

0106030100dist[n]

运行实例当前生长点：v1v0v2v3v4v11010030∞v0v2v3v4v1101003050201060当前的最短路径：<v0,v3,v2>50<v0,v3,v4>90v0v2v3v4v11030当前的最短路径：<v0,v3,v2,v4>60v0v2v3v4v11030602020105010060010503090dist[n]

010503060dist[n]

运行实例当前生长点：v3当前生长点：v2v0v2v3v4v1101003050201060voidDijkstra(intv)/*从源点v出发*/{inti,k,num,dist[MaxSize];stringpath[MaxSize];for(i=0;i<vertexNum;i++)/*初始化数组dist[n]和path[n]*/{dist[i]=edge[v][i];path[i]=vertex[v]+vertex[i];/*字符串连接*/}v0distpath下标1234终点

v1

v2

v3

v4

S10v0,v1∞v0,v230v0,v3100v0,v4算法实现v0v2v3v4v1101003050201060v0distpath下标1234终点

v1

v2

v3

v4

Sdistpathdistpathdistpathdistpath10v0,v1∞v0,v230v0,v3100v0,v4for(num=1;num<vertexNum;num++){}for(k=0,i=0;i<vertexNum;i++)

if((dist[i]!=0)&&(dist[i]<dist[k]))k=i;cout<<path[k]<<dist[k];v0,v1算法实现v0v2v3v4v1101003050201060v0distpath下标1234终点

v1

v2

v3

v4

Sdistpathdistpathdistpathdistpath10v0,v1∞v0,v230v0,v3100v0,v4v0,v10v0,v160

v0,v1,v230v0,v3100v0,v4for(num=1;num<vertexNum;num++){}for(i=0;i<vertexNum;i++)if(dist[i]>dist[k]+edge[k][i]){dist[i]=dist[k]+edge[k][i];path[i]=path[k]+vertex[i];}dist[k]=0;算法实现v0distpath下标1234终点

v1

v2

v3

v4

Sdistpathdistpathdistpathdistpath10v0,v1∞v0,v230v0,v3100v0,v40v0,v160

v0,v1,v230v0,v3100v0,v4v0,v1v0,v2,v350

v0,v3,v20v0,v390v0,v3,v4v0,v1,v3,v20

v0,v3,v260v0,v3,v2,v4v0,v1,v3,v2,v40v0,v3,v2,v4v0v2v3v4v1101003050201060验证算法voidDijkstra(intv)/*从源点v出发*/{inti,k,num,dist[MaxSize];stringpath[MaxSize];

for(i=0;i<vertexNum;i++){dist[i]=edge[v][i];path[i]=vertex[v]+vertex[i];}}

for(num=1;num<vertexNum;num++){

for(k=0,i=0;i<vertexNum;i++)

if((dist[i]!=0)&&(dist[i]<dist[k]))k=i;cout<<path[k]<<dist[k];

}O(n)时间复杂度？O(n2)O(n)O(n)

for(i=0;i<vertexNum;i++)if(dist[i]>dist[k]+edge[k][i]){dist[i]=dist[k]+edge[k][i];path[i]=path[k]+vertex[i];}dist[k]=0;O(n)算法实现5-5-2Floyd算法v第五章图每一对顶点的最短路径问题【问题】给定带权有向图G＝(V,E)，对任意顶点

vi

和vj（i≠

j），求从顶点

vi到顶点

vj的最短路径【想法1】每次以一个顶点为源点调用Dijkstra算法。显然，时间复杂度为O(n3)

【算法】Floyd算法【想法2】

。。。。。。算法：Floyd算法输入：带权有向图

G=(V，E)输出：每一对顶点的最短路径

1.初始化：假设从

vi到

vj的弧是最短路径，即dist-1(vi,vj)=w<vi,vj>；2.循环变量k

从0~n-1进行n次迭代：distk(vi,vj)=min{distk-1(vi,vj),distk-1(vi,vk)+distk-1(vk,vj)}w<vi,vj>：从顶点vi到顶点vj

的权值distk(vi,vj)：从顶点vi

到顶点vj

经过的顶点编号不大于k的最短路径长度vivjvk基本思想如何存储dist？如何存储带权有向图？邻接矩阵算法：Floyd算法输入：带权有向图

G=(V，E)输出：每一对顶点的最短路径

1.初始化：假设从

vi到

vj的弧是最短路径，即dist-1(vi,vj)=w<vi,vj>；2.循环变量k

从0~n-1进行n次迭代：

distk(vi,vj)=min{distk-1(vi,vj),distk-1(vi,vk)+distk-1(vk,vj)}dist-1(vi,vj)=w<vi,vj>distk(vi,vj)=min{distk-1(vi,vj),distk-1(vi,vk)+distk-1(vk,vj)}存储结构初始化dist-1

=04116023∞0voidFloyd(){inti,j,k,dist[MaxSize][MaxSize];for(i=0;i<vertexNum;i++)for(j=0;j<vertexNum;j++)dist[i][j]=edge[i][j];}运行实例v0v2v1346112经过v0dist0

=0411602370经过v1dist1

=046602370经过