本文共 3325 字,大约阅读时间需要 11 分钟。
还不知道图是什么的可以看看这篇:。
最短路径,即在网络(带权的图)中,求两个不同顶点之间的所有路径中,边的权值之和最小的那一条路径。第一个顶点为源点,最后一个顶点为终点。
【问题分类】
单源最短路问题(特定点到所有点的最短路)和多源最短路问题(任意两点之间的最短路)。其中又分为有向图和无向图,有权图和无权图。根据边权的正负,又分为带负权边和不带负权边的最短路。
无权图的单源最短路算法类似bfs算法的实现过程,依次遍历结点并将遍历到的现结点的所有邻接点(相邻连接的点)压入队列,继续遍历直到访问到所有结点。也可以看做是权值为1的有权图的单源最短路。
有权图的单源最短路算法:Dijkstra算法,运用了贪心的思想(类似Prim算法)。
【Dijkstra算法】
顶点的收录和最短路径的更新有两种方法。法一:直接扫描所有未收录顶点,对稠密图(边多)效果好。法二:将dist存在最小堆中,对稀疏图(边少)效果好。下面介绍法一。
【Dijkstra代码】
//时间复杂度为O(V*V+E)const int INF=0x3f3f3f3f;const int N=505;int mp[N][N]; //图的邻接矩阵int dis[N]; //源点到图中节点i的最短路径的长度int vis[N]; //判断当前点是否访问过 int n,m;void init(){ for(int i=1;i<=n;i++) //初始化 for(int j=1;j<=n;j++) if(i==j) mp[i][j]=0; else mp[i][j]=INF;}int dij(int st,int ed) //源点和终点{ for(int i=1;i<=n;i++) { dis[i]=mp[st][i]; vis[i]=0; } vis[st]=1; //收录源点 for(int i=1;i
多源最短路算法
法1:直接将单源最短路算法调用|V|遍,时间复杂度 O( |V|3 + |E|×|V|),对于稀疏图效果好。
法2:Floyd算法,对于稠密图效果好。下面介绍Floyd算法。
【Floyd算法】
//适用于多源无负权//时间复杂度O(n^3),空间复杂度O(n^2) const int INF=0x3f3f3f3f;const int N=205;int mp[N][N];int dis[N][N]; //表示i到j的最短路径长度int n,m;void init(){ for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(i==j) mp[i][j]=0; else mp[i][j]=INF;}int Floyd(int bg,int ed){ for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) dis[i][j]=mp[i][j]; for(int k=1;k<=n;k++) //枚举以k为中间点的所有点的最短路 for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]); return dis[bg][ed];}
Bellman-Ford算法与Dijkstra算法一样,可用于单源最短路问题,区别在于Bellman-Ford算法还可以解决存在负权边的问题。
【Bellman-Ford算法】
//可解决负权边,解决单源最短路径,时间复杂度O(nm),空间复杂度O(m)
//主要思想:最短路一定不含环(不论正、负、零环),所以最短路一定最多只包含n-1条边 //我们对每条边进行n-1次松弛后即为最短路 //此外,Bellman_Ford还可以检测一个图是否含有负权回路:如果在进行n-1轮松弛后仍然存在dst[e[i]] > dst[s[i]]+w[i] //建图时注意,如果是无向图,s,e,w数组应该开2*m大小,要建双向边int s[m]; //起点 int e[m]; //终点 int w[m]; //权值 int dis[n]; //源点到每个点的最短路 int blm(int st,int ed) { for(int i=1;i<=n;i++) dis[i]=INF; dis[st]=0; for(int k=1;kdis[s[i]]+w[i]) flag=true; if(flag) cout<<"存在负权回路"<
实际上,SPFA算法在国际上通称为“队列优化的Bellman-Ford算法”。
【SPFA算法】
设立一个先进先出的队列用来保存待优化的结点,优化时每次取出队首结点u,并且用u点当前的最短路估计值对u点所指向的结点v进行松弛操作,如果v点的最短路估计值有所调整,且v点不在当前的队列中,就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作,直至队列为空为止。这个算法保证只要最短路存在,SPFA算法必定能求出最小值。
//如果某个点弹出队列的次数超过n-1次,则存在负环。对于存在负环的图,无法计算单源最短路。
//玄学时间复杂度,O(E)-O(VE)之间int mp[n][n]; int n,m; int dis[n]; int vis[n]; void init() { for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(i==j) mp[i][j]=0; else mp[i][j]=INF; } int spfa(int st,int ed) { for(int i=1;i<=n;i++) { dis[i]=INF; vis[i]=0; } dis[st]=0; vis[st]=1; queue q; q.push(st); while(!q.empty()) { int now=q.front(); q.pop(); vis[now]=0; for(int i=1;i<=n;i++) if(dis[i]>dis[now]+mp[now][i]) { dis[i]=dis[now]+mp[now][i]; if(vis[i]==0) { q.push(i); vis[i]=1; } } } return dis[ed]; }
转载地址:http://ffben.baihongyu.com/