图论--最短路算法
--yangkai
在解决最短路问题时，优秀的最短路算法是必不可少的工具
在这里介绍几种实用的算法
1 Floyd
2 Dijkstra算法
3 Dijkstra+堆优化
4 Bellman-Ford
5 SPFA(Shortest Path Faster Algorithm)
0 图的储存方式
- 边目录(记下来，仅此而已)
- 邻接矩阵(适合稠密图)
-
邻接表(适合稀疏图)
-
链式前向星(万能)：
从每一个点把与之相连的边拉成一条链
用head记录下第一条边，再通过next值向后跳
手动模拟一遍代码就能理解了$\downarrow$
struct Edge{int v,w,next;}E[N];
int head[N],tot=0;
void add(int u,int v,int w){
E[++tot]=(Edge){v,w,head[u]};
head[u]=tot;
}
1 Floyd
处理多源最短路和最小环使用
在n<=500的情况下Floyd是不二之选
时间效率:$O(n^3)$
//用d[i][j]表示i到j的最短路
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
如果需要用到最小环，如下改进代码：
//用d[i][j]表示i到j的最短路
//用g[i][j]表示i到j的初始距离
for(int k=1;k<=n;k++){
for(int i=1;i<k;i++)
for(int j=i+1;j<k;j++)
mins=min(d[i][j]+g[i][k]+g[k][j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}
//求出的mins是该图的最小环
2 Dijkstra
Dijkstra算法采用贪心策略解决单源最短路
每次都查找与该点距离最近的点继续贪心
贪心的策略使得它不能用来解决存在负权边的图
时间效率:$O(n^2)$
//链式前向星储存图
//d[i] 表示起点到i的最短路
//vis 记录是否更新过当前节点
void dijkstra(int s){
for(int i=1;i<=n;i++)d[i]=INF,vis[i]=0;
d[s]=0;
for(int i=1;i<=n;i++){
int u,mins=INF;
for(int j=1;j<=n;j++)
if(!vis[j]&&d[j]<mins)u=j,mins=d[j];//找最近点
vis[u]=1;
for(int j=head[u];j;j=E[j].next)
if(d[E[j].v]<d[u]+E[i].w){
d[E[j].v]=d[u]+E[i].w;
//如果需要记录路径在此处加上 From[v]=u;
}
}
3 Dijkstra+堆优化
Dijkstra算法的时间效率$O(n^2)$并不优秀
加了堆优化时间效率变成O($nlog(n)$)十分优秀，且不容易被卡
唯一的缺点就是不能处理有负边权的图
时间效率:$O(nlog(n))$
//链式前向星储存图
//优先队列中储存的访问节点
struct Node{int id,w;};//id为节点编号,w为权重
bool operator < (Node a,Node b){
return a.w>b.w;//堆默认大根堆，反向定义
}
priority_queue<Node> q;
void Dijkstra(int s){
for(int i=1;i<=n;i++)d[i]=INF,vis[i]=0;
d[s]=0;
q.push((Node){s,0});
while(!q.empty()){
Node t=q.top();q.pop();
int u=t.id;
if(vis[u])continue;vis[u]=1;
for(int i=head[u];i;i=E[i].next){
int v=E[i].v;
if(d[v]>d[u]+E[i].w){
d[v]=d[u]+E[i].w;
//如果需要记录路径在此处加上 From[v]=u;
q.push((Node){v,d[v]});
}
}
}
}
4 Bellman-Ford
bellman-Ford利用松弛原理
对于不存在负权回路的图,最短路最多只经过n个节点
那么就可以通过n-1次松弛操作就可以得到最短路
如果可以继续松弛则有负环，所以可以判断负环
时间效率:$O(nm)$
//采用边目录的储存方式
struct Edge{int v,w;};
vector<Edge> E;
bool Bellman_Ford(int s){
d[s]=0;
for(int i=1;i<n;i++)
for(int j=0;j<E.size();j++)
if(d[E[j].v]>d[E[j].u]+E[j].w)
d[E[j].v]=d[E[j].u]+E[j].w;
//在判断负回路时，只需要重新判断是否可以松弛，如果可以则存在
for(int i=0;i<E.size();i++)
if(d[E[j].v]>d[E[j].u]+E[j].w)return true;
return false;
}
5 SPFA(Shortest Path Faster Algorithm)
用队列实现Bellman-Frod，减少其多余的松弛操作
当给定的图存在负权边，而Bellman-Ford算法的复杂度又过高，SPFA算法便成了解题利器
因为原理和Bellman-Ford相同，所以依然可以判断负环是否存在
唯一不足是会被网格图卡
时间效率:$O(nlog(n))$
//默认链式前向星储存图
queue<int> q;
bool inque[N];//记录是否在队列中 避免重复
int cnt[N];//记录入队次数 判断负环
bool SPFA(int s){
for(int i=1;i<=n;i++)inque[i]=0,cnt[i]=0,d[i]=INF;
d[s]=0;cnt[s]=1;
q.push(s);
while(!q.empty()){
int u=q.front();q.pop();
inque[u]=false;
for(int i=head[u];i;i=E[i].next){
int v=E[i].v,w=E[i].w;
if(d[v]>d[u]+w){
d[v]=d[u]+w;
if(!inque[v]){
inque[v]=true;
if(++cnt>n)return false;//判断负环
q.push(v);
}
}
}
}
return true;
}
总结
当范围小 或 用多源 或 最小环 时选择Floyd
如果不存在负环Dijkstra+堆优化稳定输出
否则SPFA快到飞起
普通的Dijkstra和Bellman-Ford因效率较低一般不采用
网友评论