浅谈图论(一)——最短路问题|江阴雨辰互联

2023年7月30日发(作者：)

浅谈图论（⼀）——最短路问题

图论〔Graph Theory〕是数学的⼀个分⽀。它以图为研究对象。图论中的图是由若⼲给定的点及连接两点的线所构成的图形，这种图形通常⽤来描述某些事物之间的某种特定关系，⽤点代表事物，⽤连接两点的线表⽰相应两个事物间具有这种关系。（摘⾃百度百科）

弗洛伊德算法这种算法解决的是多源最短路问题（求任意两点之间的最短路径）若我们⽤⼆维数组e[i][j]表⽰点i到点j当前的最短距离（程序运⾏完后数组中存的就是真正的最短距离）那么我们可以⽤e[i][j]=max(e[i][j],e[i][k],e[j][k]);来更新e数组。也就是⽐较从i到j 和从i到k+从k到j 的距离重点来啦核⼼思想：能否找到第三点使得任意两点的距离变短，即能否找到 i->k->j ⽐ i->j 短，如果能找到，就更新。下⾯呈上代码：//多元最短路 Floyd O(n^3)#include#include#include#include#include#includeusing namespace std;const int maxn=99999999;int n,m,e[1005][1005];int main(){ int i,j,k,a,b,c; scanf("%d%d",&n,&m); for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { if(i==j) e[i][j]; else e[i][j]=maxn; } } for(i=1;i<=m;i++) { scanf("%d%d%d",&a,&b,&c); e[a][b]=c; } //Floyd核⼼部分

for(i=1;i<=n;i++) for(j=1;j<=n;j++) for(k=1;k<=n;k++) if(e[j][k]>e[j][i]+e[i][k]) e[j][k]=e[j][i]+e[i][k]; for(i=1;i<=n;i++) { for(j=1;j<=n;j++) printf("%d ",e[i][j]); printf("n"); } return 0;}Floyd很容易发现Floyd算法的时间复杂度是O(N^3)。这个复杂度很⾼，时间限制为1000ms的情况下，n=1000左右就不⾏了。但它的优点是好写，好理解，可以解决负边权。总结⼀下Floyd：时间复杂度：O(N^3)优点：好写，好理解，可以解决负边权缺点：太慢

ra 迪杰斯特拉这种算法解决的是单源最短路问题（求任意⼀点与其它点之间的最短路径）这种算法也要⽤e数组，作⽤同上本算法还要⽤dis数组，我们⽤dis[i]表⽰点i到源点当前的最短距离，这个值是不断变化的个⼈感觉Dijkstra⽐Floyd要难⼀点⽅法：1.我们可以把所有的点分为两个集合，集合p和集合q，⽤数组book表⽰。book[i]==1的为p表⽰选过的点，book[j]==0为q表⽰没选过的点.；2.从q集合中选择⼀个离源点最近的点，即使dis[u]最⼩，将该点u加⼊p集合。并搜索每⼀条以u为起点的边进⾏松弛，即⽐较dis[v]和dis[u]+e[u][v]；3.重复第2步，直到q集合为空。此时dis数组中存的就是最终结果。下⾯呈上代码：（默认源点为1号顶点）#include#include#include#include#include#includeusing namespace std;const int maxn=99999999;int n,m,e[1005][1005],dis[1005],book[1005];

int main(){ int i,j,a,b,c; scanf("%d%d",&n,&m); for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { if(i==j) e[i][j]; else e[i][j]=maxn; } } book[1]=1; for(i=1;i<=m;i++) { scanf("%d%d%d",&a,&b,&c); e[a][b]=c; } for(i=1;i<=n;i++) dis[i]=e[1][i]; for(i=1;i<=n-1;i++) { int minn=maxn,u; for(j=1;j<=n;j++) { if(dis[j]dis[u]+e[u][j]) dis[j]=dis[u]+e[u][j]; }

} } for(i=1;i<=n;i++) printf("%d ",dis[i]); return 0;}Dijkstra Dijkstra的时间和空间复杂度都是O(n^2)此外，我们发现Dijkstra在找到u点后需要把图扫⼀遍，所以可以⽤邻接表来优化下⾯呈上Dijkstra邻接表优化的代码：#include#include#include#include#include#includeusing namespace std;const int maxn=99999999;int n,m,dis[1005],book[1005];int b[1005],c[1005];int first[1005],next[1005];

int main(){ int i,j,x,y,z; scanf("%d%d",&n,&m); //book[1]=1; for(i=1;i<=m;i++)//建⽴邻接表

{ scanf("%d%d%d",&x,&y,&z); b[i]=y; c[i]=z; next[i]=first[x];//建表的关键

first[x]=i; } memset(dis,88,sizeof(dis)); dis[1]=0; //Dijkstra的核⼼部分

for(i=1;i<=n-1;i++) { int minn=maxn,u; for(j=1;j<=n;j++) { if(dis[j]

n-Ford 贝尔曼福德算法个⼈最喜欢的最短路算法（同感的点个赞呗）这种算法解决的也是单源最短路问题。这种算法也需要dis数组，作⽤同上。⽅法：1.枚举每⼀条边，⽐如说u->v的边，看看能否通过该边使得dis[v]变短,即⽐较dis[v]和dis[u]+c[i]（c为路径长度）2.重复步骤1，每重复⼀遍称为⼀遍松弛那么需要松弛多少次呢？n-1次。因为任意两点之间的路径最多经过n-1条边。敲⿊板划重点：最短路径中不可能包含回路！

讲完了，呈上代码：#include#include#include#include#include#includeusing namespace std;int n,m,a[10005],b[10005],c[10005],dis[10005];int main(){ int i,j; memset(dis,88,sizeof(dis)); dis[1]=0; scanf("%d%d",&n,&m); for(i=1;i<=m;i++) scanf("%d%d%d",&a[i],&b[i],&c[i]); for(i=1;i<=n-1;i++) { for(j=1;j<=m;j++) { if(dis[b[j]]>dis[a[j]]+c[j]) { dis[b[j]]=dis[a[j]]+c[j]; } } } for(i=1;i<=n;i++) printf("%d ",dis[i]); return 0;}Bellman-FordBellman-Ford此外，Bellman-Ford算法还能判断⼀个图有没有负权回路，如果松弛完了之后仍存在dis[b[j]]>dis[a[j]]+c[j]则此图有负权回路，因为从负权回路⾛⼀圈可以使最短路径再次变短。有⼈可能会问了：真的必须要松弛n-1次吗？答案是：不需要！n-1次只是⼀个最⼤值罢了。如果当前的⼀轮松弛没有作⽤，那么后⾯的都不会起作⽤，此时可以提前跳出循环我们将上⾯⼏⾏的描述加⼊到代码中，如下：#include#include#include#include#include#includeusing namespace std;int n,m,a[10005],b[10005],c[10005],dis[10005];int main(){ int i,j,check; memset(dis,88,sizeof(dis)); dis[1]=0; scanf("%d%d",&n,&m); for(i=1;i<=m;i++) scanf("%d%d%d",&a[i],&b[i],&c[i]); for(i=1;i<=n-1;i++) { check=0; for(j=1;j<=m;j++) { if(dis[b[j]]>dis[a[j]]+c[j]) { dis[b[j]]=dis[a[j]]+c[j]; check=1; } } if(check==0) break; } for(j=1;j<=m;j++) if(dis[b[j]]>dis[a[j]]+c[j]) { printf("此图有负权回路"); return 0; } for(i=1;i<=n;i++) printf("%d ",dis[i]); return 0;}Bellman-Ford优化版此外，Bellman-Ford算法还有⼀种队列优化⽅法：每次仅对最短路估计值发⽣变化了的顶点的所有出边执⾏松弛操作。我们可以⽤⼀个队列来维护这些点，⽤邻接表来储存图下⾯呈上代码：#include#include#include#include#include#include#includeusing namespace std;int n,m,a[1005],b[1005],c[1005],dis[1005],book[1005],first[1005],next[1005];int main(){ int i,x,y,z; queue Q; scanf("%d%d",&n,&m); for(i=1;i<=m;i++) { scanf("%d%d%d",&x,&y,&z); a[i]=x; b[i]=y; c[i]=z; next[i]=first[x]; first[x]=i; } memset(dis,88,sizeof(dis)); dis[1]=0; (1); book[1]=1; while(!()) { for(i=first[()];i;i=next[i]) { if(dis[b[i]]>dis[a[i]]+c[i]) { dis[b[i]]=dis[a[i]]+c[i]; if(book[b[i]]==0) { (b[i]); book[b[i]]=1; } } } book[()]=0; (); } for(i=1;i<=n;i++) printf("%d ",dis[i]); return 0;}Bellman-Ford队列优化SPFA