最短路学习笔记
图的存储
邻接矩阵
初始化 G[i][j]=inf
G[i][j] = v 表示 从点i与点j有边,权值为v;
有向图存一遍,无向图存两遍,重边取最小(吧)
适用于稠密图
领接表
定义一个Last[N]数组用于存储某点最新连接的边号
int Last [N],cnt = 0;
struct Edge{
int to,v,next;
} E[M] ;
加边:
inline void add (int from,int to,int v) {
cnt++;
E[cnt].next = Last [from];
Last [from] = cnt;
E[cnt].to = to;
E[cnt].v = v;
}
适用稀疏图
注意,在无向图中,领接表存储边的数组应开到双向边的2倍
inf表示一个极大值;
1. Floyd-Warshall
时间复杂度O(n^3) 空间复杂度O(n^2)
一般使用邻接矩阵实现
初始化时,任意两条路为无现长(极大,但应使该值得两倍不超过int范围)。
与自己连接的长度为0
int G[MAXN][MAXN];
for(int k=1;k<=N;++k)
for(int i=1;i<=N;++i)
for(int j=1;j<=N;++j)
G[i][j]=std::max(G[i][j],G[i][k]+G[k][j]);
理解:
如果求从A至B的最短路,不断寻找一个点K,使得从A到K,再从K到B的总路程最短。
Floyd-Warshall算法不能解决带有“负权回路”(或者叫“负权环”)的图
因为带有“负权回路”的图没有最短路
但可以解决带有负权的问题
## 2.Dijkstra
时间复杂度(N^2) 空间复杂度(M)
初始化 (以下初始化默认为此方式):
Last[N],E[M];
int From //出发点的编号
int v[N] //记录该点是否已经使用
int dist[N] //表示出发点至各点的距离;
for(int i=1;i<=n;i++) dist[i]=inf;
dist[From]=0;
for(int i=Last[From];i;i=E[i].next){
int To=E[i].to; //所连接的点
dist[To]=E[i].v;
}
寻找最短路:
for(int q=1;q<=n-1;++q){
int min=inf; //初始化最小值
int M; //记录目前最短路的
for(int i=Last[From];i;i=E[i].next){
int To=E[i].to;
if(min>dis[To]&&!v[To]){
min=dis[M=To];
v[To]=1
}
}
for(int i=Last[M];i;i=E[i].next){
int To=E[i].to;
dis[To]=std::min(dis[To],dis[M]+E[i].v);
}
}
理解:
1.将点分为两部分
(1).已知最短路径的集合P
(2).未知最短路径的集合Q
2.在点P中寻找一个点M与From点的距离最短,并将M标记;
3.以M为出发点,将从M出发连接的点i的距离E[i].v加上dis[M]的距离,如果比dis[ i]小,即将新距离视为为From到i的最短距离
4.重复 2~3 n-1次 (最短路中共有n-1条边(最多为n-1次,实际起作用的可能更少);
对于边数M小于N2的稀疏图,是用领接表较优,反之适用邻接矩阵
不可以对具有负权的图使用
堆优化
最优复杂度 ((N+M)logN)
维护堆kogN 边历图N+M
初始化与上文相同
struct heap{
int node,v;
bool operator < (const heap &M) const{
return v>m.v;
}
priority_queue<heap> q;
q.push((heap){From,0);
while(!q.empty()){
heap Now=q.top();q.pop();
int M=Now.node,V=Now.v;
if(v[M]) continue;
v[M]=1;
for(int i=Last[M];i;i=E[i].next){
int To=E[i].to;
if(dis[To]>dis[M]+E[i].v){
dis[To]=dis[M]+E[i].v;
q.push((heap){To,dis[To]);
}
}
}
在朴素的Dijkstra算法中,我们使用大量时间寻找目前与From最短距离的点,这一需求可以使用最小堆实现。
3.Bellman-Ford
时间复杂度(NM) 空间复杂度(M)
在存边中存入始发点的信息
struct Edge{
int from,to,next,v;
}E[M];
寻找最短路
for(int i=1;i<=N-1;++i){
for(int j=1;j<=cnt;++j){
int From=E[j].from,To=E[j].to,V=E[j].v;
if(dis[To]>dis[From]+V)
dis[To]=dis[From]+V;
}
}
检测负回路
for(int j=1;j<=cnt;++j){
int From=E[j].from,To=E[j].to,V=E[j].v;
if(dis[To]>dis[From]+V)
dis[To]=dis[From]+V;
}
理解
通过查看第i条边,验证能否通过第i条边使出发点到To的距离缩短
如果在更新N-1后仍可以更新最短路,那说明存在负回路
关于最短路中回路的讨论
如果最短路中存在正回路,那说明至少有一条边走过两次
若只走一次比会得到比当前包含正回路的最短路更短的方案
如果最短路中存在负回路,那可以通过无限通过负回路使最短路变为无限小,无限小的最短路即不存在最短路
关于N-1的讨论
一个最短路中最多有N-1条边(最小生成树)
最短路与最小生成树的区别
最小生成树是计算从一节点到另一节点的最小边集;
最短路是带权路径,计算权值最小
最小生成树要经过每一个点,
最短路只需要能达到某两点,路径权值最小即可。
3 (2). SPFA
最劣时间复杂度(NM) 空间复杂度(M)
期望时间复杂度:O(kM), 其中k为所有顶点进队的平均次数,可以证明k一般小于等于2
queue<int> q;
q.push(k),v[k]=1,dis[k]=0;
while(!q.empty()){
int Now=q.front();q.pop();v[Now]=0;
for(int i=last[now];i;i=e[i].next){
if(dis[E[i].to]>dis[Now]+E[i].v){
dis[E[i].to]=dis[Now]+E[i].v;
if(!E[e[i].to])
q.push(e[i].to),v[e[i].to]=1;
}
}
}
理解
如果一个点进入队列N次,那么该图必存在负环
一个顶点在出队后可能再被放入队列,也就是当一个顶点的最短路程估计值变小后,需要对其所有出边进行松弛
但是如果这个顶点最短路程估计值再次变小,仍需要对其所有出边进行松弛,才能保证相邻顶点最短路程同步更新。
所以只有在前一遍松弛中改变了最短路程的顶点,才可能通过该顶点出边所连接的顶点的最短路更新。
使用队列存储,便可以记录在前面松弛中改变了最短路的顶点。
降低了复杂度
其他
SPFA算法有两个优化策略SLF和LLL
SLF:Small Label First 策略,设要加入的节点是j,队首元素为i,若dist(j)<dist(i),则将j插入队首,否则插入队尾;
LLL:Large Label Last 策略,设队首元素为i,队列中所有dist值的平均值为x,若dist(i)>x则将i插入到队尾,查找下一元素,直到找到某一i使得dist(i)<=x,则将i出队进行松弛操作。
SLF 可使速度提高 15 ~ 20%;SLF + LLL 可提高约 50%。
在实际的应用中SPFA的算法时间效率不是很稳定,为了避免最坏情况的出现,通常使用效率更加稳定的Dijkstra算法。
比较
Floyd | Dijkstra | Dijkstra(heap) | Bellman-Ford | SPFA |
---|---|---|---|---|
稠密图 与顶点相关 | 稠密图 与顶点相关 | 稠密图 与顶点相关 | 稀疏图 与边关系密切 | 稀疏图 与边关系密切 |
可以解决负权 | 无法解决负权 | 无法解决负权 | 可以解决负权 | 可以解决负权 |
Dijkstra:O(n2)适用于权值为非负的图的单源最短路径,用斐波那契堆的复杂度O(M+NlogN),
BellmanFord:适用于权值有负值的图的单源最短路径,并且能够检测负圈,复杂度O(MN)
SPFA:适用于权值有负值,且没有负圈的图的单源最短路径,论文中的复杂度O(kE),k为每个节点进入Queue的次数,且k一般<=2,但此处的复杂度证明是有问题的,其实SPFA的最坏情况应该是O(MN).
Floyd:每对节点之间的最短路径。Floyd-Warshall算法的时间复杂度为O(N^3),空间复杂度为O(N^2)。
先给出结论:
(1)当权值为非负时,用Dijkstra。
(2)当权值有负值,且没有负圈,则用SPFA,SPFA能检测负圈,但是不能输出负圈
。
(3)当权值有负值,而且可能存在负圈,则用BellmanFord,能够检测并输出负圈。
(4)SPFA检测负环:当存在一个点入队大于等于V次,则有负环.
本文借鉴了部分网络博客与《啊哈,算法》的内容
如有不足或错误欢迎交流
本文出自MayFlyyh's Blog,转载时请注明出处及相应链接。
本文永久链接: http://www.mayflyyh.com/archives/37
一条评论
%%%