数据结构：最短路径算法

图算法（二）最短路经ShortestPath青岛理工大学acm2023/2/51Dijkstra算法练习题链接/vjudge/contest/view.action?cid=29337#overviewFloyd算法练习题链接/vjudge/contest/view.action?cid=29305#overview密码都是：6712023/2/52/sjjg/DataStructure/DS/web/flashhtml/Dijkstra.htm这个链接是Dijskra算法的动态演示2023/2/53问题:两地之间是否有通路?若存在多条通路，哪条路最短？最短路径问题2023/2/54单源最短路径

Single-SourceShortestPath(Dijkstra算法)所有顶点对间的最短路径问题

All-PairsShortestpaths

（Floyd算法）

最短路径问题2023/2/55单源最短路径

Single-SourceShortestPath问题:带权有向图G（E,V),找出从给定源顶点s到其它顶点v的权最小路径。

“最短路径”=最小权路径的权是路径上所有边的权之和。例：道路图:从青岛理工到金沙滩的最短路径?2023/2/56v5v4v01005601010v1v2v3205030图中从v0到其余各顶点之间的最短路径:v0到v1无

v0到

v2(v0,v2)10v0到

v3(v0,v4,

v3)50v0到

v4(v0,v4)30v0到

v5(v0,v4,

v3,v5)60单源最短路径2023/2/57贪心算法：

若顶点序列{V0,V1,…,Vn}是从V0到Vn的最短路，则序列{V0,V1,…,Vn-1}必为从V0到Vn-1的最短路。权非负的单源最短路径算法（Dijkstra）2023/2/58基本思想：将图中所有顶点分成两组:S,V-S

一组是包括已确定最短路径的顶点的集合S，另一组是尚未确定的最短路径的顶点集V-S。

S初始仅包含源v0,不断在V-S做贪心选择扩充集合S。权非负的单源最短路径算法（Dijkstra）2023/2/59权非负的单源最短路径算法（Dijkstra）

初始时,S仅包含源v0,

特殊路径：

从源到G中某一顶点u且中间只经过S中顶点的路称为从源到u的特殊路径。步骤:(1)取v0加入S中

(2)从V-S中取出具有当前最短路径长度的顶点w加入S中。2023/2/510v5v4v0100601010v1v3205030v2v0

v1

v2

v3

v4

v5v0

v1

v2

v3

v4

v5权非负的单源最短路径算法（Dijkstra）邻接矩阵2023/2/511v0到其它各点的最短路

i=1i=2i=3i=4i=5初始时v0∞10∞30100v2∞10∞30100v4∞10503090v3∞30503060v5∞30503060v1∞305030602023/2/512Dijkstra算法：一般情况下，Dist[k]=<源点到顶点i的弧上的权值>

或者=<源点到其它顶点的路径长度>+<其它顶点到顶点i的弧上的权值>

设置辅助数组Dist，其中每个分量Dist[i]表示

当前所求得的从源点到其余各顶点i的最短路径的长度。2023/2/5131）在所有从源点出发的弧中选取一条权值最小的弧，即为第一条最短路径。2）修改其它各顶点的Dist[i]值。假设求得最短路径的顶点为u，若Dist[u]+G.arcs[u][i]<Dist[i]则将Dist[i]改为Dist[u]+G.arcs[u][i]V0和i之间存在弧V0和i之间不存在弧其中的最小值即为最短路径的长度。2023/2/514权非负的单源最短路径算法（Dijkstra）#include<iostream>#include<string.h>#include<stdio.h>usingnamespacestd;constintINF=0xfffffff;#definemaxn110int

grap[maxn][maxn];//邻接矩阵存储图int

pre[maxn];//标记这个点是否已经被选过intn,m;int

dist[maxn];//记录从源点到其他所有点的最短距离2023/2/515voidinit()//对一些数据进行初始化{inti,j;

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

grap[i][j]=INF;

memset(pre,0,sizeof(pre));}voiddijkstra(intu){

inti,j;

for(i=1;i<=n;i++)//首先求出源点到其他所有点的距离

dist[i]=grap[u][i];

pre[u]=1;2023/2/516

intx=u;

for(i=1;i<n-1;i++) {int

maxs=INF;

for(j=1;j<=n;j++)//类似于最小生成树prim算法，找到距离最短的那个点

if(!pre[j]&&maxs>dist[j]) {

maxs=dist[j]; x=j; }

pre[x]=1;

for(j=1;j<=n;j++)//然后再通过这个点去得到其他点的最短距离

if(!pre[j]&&dist[j]>(dist[x]+grap[x][j])&&grap[x][j]<INF)

dist[j]=grap[x][j]+dist[x]; }}2023/2/517intmain(){

scanf("%d%d",&n,&m); init();

inti,x,y,z;

for(i=0;i<m;i++)//对有向图进行存储

{

scanf("%d%d%d",&x,&y,&z);

grap[x][y]=z; } dijkstra(1);//假设求点1到其他点的最短路

return0;}2023/2/518所有顶点对之间的最短路径算法Floyd算法已知一个有向图（无向图），对于每对顶点Vi！=Vj

，求出它们之间的最短路径长度。解决这个问题有两种方法：（1）轮流以每个顶点为源点重复执行dijkstra算法。（2）采用Floyd算法，时间复杂度O（n3）

2023/2/519例13226431104116023∞

0初始a：P=000000046602370a2=0411602370k=1a1=k=2k=30465023700-10P1=000000010002000010002300010P2=P3=a3=Floyd算法演示2023/2/520Floyd算法描述定义一个n阶的方阵序列：A（-1），A（0）A（1）……A（n-1），其中：A（-1）[i][j]表示顶点vi到vj的直接边长，A（-1）就是存储图的邻接矩阵Edge[n][n]A（0）[i][j]表示从顶点vi到vj，中间顶点是v0的最短路径长度A（1）[i][j]表示从顶点vi到vj，中间顶点序号不大于1的最短路径长度………..A（k）[i][j]表示从顶点vi到vj，中间顶点序号不大于k的最短路径长度..........2023/2/521A（n-1）[i][j]是最终求得的从顶点vi到vj的最短路径长度增加中间顶点vk后，对于图中的每一对顶vi和vj，要比较从vi到vk的最短路径长度加上从vk到vj的最短路径长度是否小于原来从vi到vj的最短路径长度，即比较A（k-1）[i][k]+A（k-1）[k][j]与A（k-1）[i][j]的大小，去较小的为A（k-1）[i][j]的值。因此我们得到递推公式为：2023/2/522Floyd算法的代码实现#include<iostream>#include<string.h>#include<stdio.h>#include<algorithm>#include<queue>usingnamespacestd;constintINF=0xfffffff;#definemaxn110int

grap[maxn][maxn];//邻接矩阵存储图intn,m;int

dist[maxn][maxn];//记录从所有点之间的最短距离2023/2/523voidinit()//对一些数据进行初始化{inti,j;

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

grap[i][j]=INF;}voidfloyd(){inti,j,k;

for(i=1;i<=n;i++)//初始化，一开始每个点与点之间的路径长度就等于grap中的长度

for(j=1;j<=n;j++)

dist[i][j]=grap[i][j];

for(k=1;k<=n;k++)

for(i=1;i<=n;i++)

for(j=1;j<=n;j++) {if(k==i||k==j)continue;

if(dist[i][k]+dist[k][j]<dist[i][j])

dist[i][j]=dist[i][k]+dist[k][j]; }}2023/2/524intmain(){

scanf("%d%d",&n,&m); init();

inti,x,y,z