算法学习--最短路问题

简介: 算法学习--最短路问题

最短路问题的难点在于建图



我们规定 n:点数 m:边数

一 朴素 Dijkstra 算法 (适应于稠密图,图可以使用邻接矩阵来存)O(n2)

Dijkstra 算法是基于贪心的,每一步都取距离最近的点

1) 初始化 dist[1]=0 dist[...]=+INF 设集合s: 所有当前已确定的点
2)
  for i:1~n
    取出不在 s 中的距离最近的点到 t (这一步可以使用优先队列来优化,就变成了堆优化 Dijkstra 算法)
    把 t 放入 s 中, 用 t 去更新其他点的距离


模板题

AcWing 849. Dijkstra 求最短路 I

#include<iostream>
#include<cstring>
using namespace std;
const int NN=510;
const int INF=1e9;
int n,m;
int g[NN][NN]; // 邻接矩阵,用来存储图
int dist[NN];     // d[x]表示为起点到达x点的最短距离
bool st[NN];   // 表示那些点已经走过了
int dijkstra(){
    memset(dist, 0x3f, sizeof dist);
    dist[1]=0;
    for(int i=1;i<=n;i++){ // 循环n次
        // 找到当前还没有走过且离起点最近的点 t
        int t=-1;
        for(int j=1;j<=n;j++){
            if(!st[j] && (t==-1 || dist[j]<dist[t])){
                t=j;
            }
        }
        st[t]=true; // t已经走过了, 做一个标记
        // 以 t 为根据, 尝试更新其他点, 看一下是直接到j点近, 还是经过t点到j点近
        // 起点 ----> j
        //   |        ^
        //   v        |
        //   ----t-----
        for(int j=1;j<=n;j++){
            dist[j]=min(dist[j], dist[t]+g[t][j]);
        }
    }
    if(dist[n]>=INF)
        return -1;
    else
        return dist[n];
}
int main(){
    cin>>n>>m;
    memset(g, 0x3f, sizeof g);
    for(int i=1;i<=m;i++){
        int x,y,z;
        scanf("%d%d%d", &x, &y, &z);
        g[x][y]=min(g[x][y],z); // 图中可能有重边,就去路径最短的点
    }
    cout<<dijkstra()<<endl;
    return 0;
}


其他题目

2662. 前往目标的最小代价 - 力扣(LeetCode)

二 堆优化 Dijkstra 算法 (适应于稀疏图,图用邻接表来存)O(m⋅logn)

1) 初始化 dist[1]=0 dist[...]=+INF 设集合s: 所有当前已确定的点
2)
  queue <- 起点
  while queue 不为空
    从优先队列 queue 中取出距离最小的点 t
    把 t 放入 s 中, 用 t 去更新其他点x的距离, 如果 x 发生了更新, 才把放入 queue


模板题 850. Dijkstra 求最短路 II - AcWing 题库

#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;
typedef pair<int,int> PII;
const int NN=1.5e5+10;
vector<PII> g[NN];
int dist[NN];
bool st[NN];
int n,m;
// heap中的pair : first 某点到起点的距离
//              : second 这个点的编号
// g 中的pair : first 某条边的长度
//            : second 这条边的终点编号
int dijkstra(){
    memset(dist, 0x3f, sizeof dist);
    dist[1]=0;
    priority_queue<PII, vector<PII>, greater<PII>> heap; // 小顶堆, 使用小顶堆来快速找到满足条件的t,
                                                         // 而不是像朴素Dijkstra那样去循环
    heap.push({0,1});
    while(!heap.empty()){
        PII t=heap.top();
        heap.pop();
        int idx=t.second;
        if(st[idx])
            continue;
        st[idx]=true;
        for(auto it: g[idx]){
            int nidx=it.second;
            int nd=it.first;
            // 只有发生更新的点才入队,因为只有发生更新的点的后继节点才有发生更新的可能
            if(dist[idx]+nd<dist[nidx]){
                dist[nidx]=dist[idx]+nd;
                heap.push({dist[nidx], nidx});
            }
        }
    }
    return dist[n]>=0x3f3f3f3f ? -1 : dist[n];
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y,z;
        scanf("%d%d%d", &x,&y,&z);
        g[x].push_back({z,y}); // 把距离放在pair的first位置上,方便在堆中排序
    }
    cout<<dijkstra()<<endl;
    return 0;
}

三 Bellman-Ford 算法 (存边的方式会比较灵活,可以使用结构体) O(n⋅m)

Bellmain-Ford 算法可以处理负权边, 但是有负权边则最短路径不一定存在

有边数限制的话只能用 Bellman-Ford 算法

1) 初始化 dist[1]=0 dist[...]=+INF
2)
  for n 次
    备份 dist -> backup
    for 所有边 a,b,w (a--w->b)
      dist[b] = min(dist[b], backup[a]+w)


为了保证一定使用的是上次迭代的数据来更新本次迭代, 这里一定要备份,否则有可能发生串联混乱

迭代 k 次表示经过不超过 k 条边, 如果迭代 n 次时, dist 还有更新, 说明有一条路径上有 n 条边, 而无环图最多有 n-1 条边, 有抽屉原理可知路径上一定有环

模板题 853. 有边数限制的最短路 - AcWing 题库

#include<iostream>
#include<cstring>
using namespace std;
const int NN=1e4+10;
struct Edge{
    int a, b, w;
} edges[NN];
int n,m,k;
int dist[NN];
int backup[NN];
void bellman_ford(){
    memset(dist, 0x3f, sizeof dist);
    dist[1]=0;
    for(int i=1;i<=k;i++){ // 把最短路径的边数限制为k
        memcpy(backup, dist, sizeof dist);
        for(int j=1;j<=m;j++){
            int a,b,w;
            a=edges[j].a,b=edges[j].b, w=edges[j].w;
            dist[b]=min(dist[b], backup[a]+w);
        }
    }
    if(dist[n]>=0x3f3f3f3f/2)
        cout<<"impossible"<<endl;
    else
        cout<<dist[n]<<endl;
}
// bellman-ford 算法可以解决有边数限制的问题
int main(){
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++){
        int x,y,z;
        scanf("%d%d%d", &x,&y,&z);
        edges[i]={x,y,z};
    }
    bellman_ford();
    return 0;
}

四 SPFA 算法 (是对 Bellman-Ford 算法的改进, SPFA 算法要求不能有负环) O(m) 最坏 O(n⋅m)


在 Bellman-Ford 算法中 dist[b] = min(dist[b], backup[a]+w) 只有 backup[a] 变小, dist[b] 才有可能变小,可以在一个 queue 中存所有变小的 a 也就是说只有一个点变小了, 这个点的后继点才有可能变小

1) 初始化 dist[1]=0 dist[...]=+INF 使用一个 bool st[] 来记录某个点是否在 queue 中
2)
  queue <- 起点
    while queue 不空
      (1) t <- q.front() q.pop()
      (2) 更新 t 的所有出边 t--w->b
          如果 b 发生了更新且不在 queue 中, 则 queue <- b


可以看出 SPFA 算法不断只有当所有点都不发生更新的时候才会停止, 如果图中有负环的话, 则会始终有点发生更新, 就会产生死循环


模板题 851. spfa 求最短路 - AcWing 题库

#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;
typedef pair<int,int> PII;
const int NN=1e5+10;
int n,m;
vector<PII> g[NN];
int dist[NN];
bool st[NN];
void spfa(){
    memset(dist, 0x3f, sizeof dist);
    dist[1]=0;
    queue<PII> que;
    que.push({0,1}); // 起点入队
    st[1]=true;
    while(!que.empty()){
        auto t=que.front();
        que.pop();
        int idx=t.second;
        int d=t.first;
        st[idx]=false; // 出队的点 st 还会被重新设为 false, 这就意味着后面这个点还有重新入队的机会, 这一点与 Dijkstra 不同
        for(auto it:g[idx]){
            int nidx=it.second;
            int nd=it.first;
            if(dist[nidx]>dist[idx]+nd){
                dist[nidx]=dist[idx]+nd;
                // 只有发生更新而且不在que中的点才能入队
                if(!st[nidx]){
                    que.push({dist[nidx], nidx});
                    st[nidx]=true;
                }
            }
        }
    }
    if(dist[n]>=0x3f3f3f3f/2){ // 因为存在负权边,所以要把无穷大的条件放宽一点
        cout<<"impossible"<<endl;
    }else{
        cout<<dist[n]<<endl;
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y,z;
        scanf("%d%d%d", &x,&y,&z);
        g[x].push_back({z,y});
    }
    spfa();
    return 0;
}


SPFA 算法也可以用来判断是否存在负环

1) dist[x] 最短距离 cnt[x] 边数
2) 我们 在更新 dist[x] 的时候, 同时记录 cnt[x] 当有 cnt[x]>=n 时,说明存在负环


五 Floyd 算法 (可以用来解决多源汇最短路问题 使用邻接矩阵来存所有的边)

1) 初始化 dist[i,i]=0 dist[i,j]=+INF
2)
  for k : 1~n
    for i : 1~n
      for j : 1~n
        d[i,j] = min(d[i,j], d[i,k]+d[k,j])


公式d[i,j] = min(d[i,j], d[i,k]+d[k,j])是由公式d[k,i,j]=d[k-1,i,k]+d[k-1,k,j]优化空间而来


模板题 854. Floyd 求最短路 - AcWing 题库

#include<iostream>
#include<cstring>
using namespace std;
const int NN=210;
int n,m,k;
int dist[NN][NN]; // dist[i][j]记录从i到j点的最短距离
void floyd(){
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
            }
        }
    }
}
int main(){
    cin>>n>>m>>k;
    memset(dist, 0x3f, sizeof dist);
    for(int i=1;i<=n;i++){
        dist[i][i]=0;
    }
    for(int i=1;i<=m;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        dist[x][y]=min(dist[x][y],z);
    }
    floyd();
    for(int i=1;i<=k;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        if(dist[x][y]>=0x3f3f3f3f/2){
            cout<<"impossible"<<endl;
        }
        else{
            cout<<dist[x][y]<<endl;
        }
    }
    return 0;
}



相关文章
|
2月前
|
存储 算法 Go
算法学习:数组 vs 链表
算法学习:数组 vs 链表
36 0
|
2月前
|
机器学习/深度学习 算法 PyTorch
【从零开始学习深度学习】43. 算法优化之Adam算法【RMSProp算法与动量法的结合】介绍及其Pytorch实现
【从零开始学习深度学习】43. 算法优化之Adam算法【RMSProp算法与动量法的结合】介绍及其Pytorch实现
|
11天前
|
机器学习/深度学习 人工智能 资源调度
【博士每天一篇文献-算法】连续学习算法之HAT: Overcoming catastrophic forgetting with hard attention to the task
本文介绍了一种名为Hard Attention to the Task (HAT)的连续学习算法,通过学习几乎二值的注意力向量来克服灾难性遗忘问题,同时不影响当前任务的学习,并通过实验验证了其在减少遗忘方面的有效性。
28 12
|
4天前
|
算法 Java
掌握算法学习之字符串经典用法
文章总结了字符串在算法领域的经典用法,特别是通过双指针法来实现字符串的反转操作,并提供了LeetCode上相关题目的Java代码实现,强调了掌握这些技巧对于提升算法思维的重要性。
|
6天前
|
算法 NoSQL 中间件
go语言后端开发学习(六) ——基于雪花算法生成用户ID
本文介绍了分布式ID生成中的Snowflake(雪花)算法。为解决用户ID安全性与唯一性问题,Snowflake算法生成的ID具备全局唯一性、递增性、高可用性和高性能性等特点。64位ID由符号位(固定为0)、41位时间戳、10位标识位(含数据中心与机器ID)及12位序列号组成。面对ID重复风险,可通过预分配、动态或统一分配标识位解决。Go语言实现示例展示了如何使用第三方包`sonyflake`生成ID,确保不同节点产生的ID始终唯一。
go语言后端开发学习(六) ——基于雪花算法生成用户ID
|
11天前
|
存储 机器学习/深度学习 算法
【博士每天一篇文献-算法】连续学习算法之HNet:Continual learning with hypernetworks
本文提出了一种基于任务条件超网络(Hypernetworks)的持续学习模型,通过超网络生成目标网络权重并结合正则化技术减少灾难性遗忘,实现有效的任务顺序学习与长期记忆保持。
14 4
|
11天前
|
存储 机器学习/深度学习 算法
【博士每天一篇文献-算法】连续学习算法之RWalk:Riemannian Walk for Incremental Learning Understanding
RWalk算法是一种增量学习框架,通过结合EWC++和修改版的Path Integral算法,并采用不同的采样策略存储先前任务的代表性子集,以量化和平衡遗忘和固执,实现在学习新任务的同时保留旧任务的知识。
50 3
|
12天前
|
存储 机器学习/深度学习 算法
【博士每天一篇文献-综述】基于脑启发的连续学习算法有哪些?附思维导图
这篇博客文章总结了连续学习的分类,包括经典方法(重放、正则化和稀疏化方法)和脑启发方法(突触启发、双系统启发、睡眠启发和模块化启发方法),并讨论了它们在解决灾难性遗忘问题上的优势和局限性。
13 2
|
1月前
|
机器学习/深度学习 数据采集 算法
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机回归模型(SVR算法)项目实战
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机回归模型(SVR算法)项目实战
|
1月前
|
机器学习/深度学习 数据采集 算法
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机分类模型(SVC算法)项目实战
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机分类模型(SVC算法)项目实战

热门文章

最新文章