AcWing
  • 首页
  • 活动
  • 题库
  • 竞赛
  • 应用
  • 其它
    • 题解
    • 分享
    • 商店
    • 问答
  • 吐槽
  • 登录/注册

图论算法--单源最短路径(Dijkstra)

作者: 作者的头像   lrx2020 ,  2023-01-24 18:30:53 ,  所有人可见 ,  阅读 36


0


单源最短路径(Dijkstra)

Dijkstra 算法基本流程:
1.初始化dist[1] = 0,其节点的dist标记为正无穷大。
2.找出一个未标记的,dist[x]最小的节点x,然后标记节点x。
3.扫描节点x的所有出边(x,y,z),若dist[y]>dist[x]+z,更新dist[y]。
4.重复2-3两个步骤,直到所有节点都被标记。
Dijkstra算法是基于贪心算法,它只适用于所有便都是非负整数的图。

#include <iostream>
#include <cstring> 

using namespace std;
const int N = 1001;
int g[N][N];
int dist[N];
bool st[N];
int n,m;

void dijkstra(){
    memset(dist,0x3f,sizeof(dist));
    dist[1] = 0;
    for(int i=1;i<=n-1;i++){
        int x = 0;
        for(int j=1;j<=n;j++){
            if(!st[j]&&(dist[j]<dist[x]||x==0)){
                x = j;
            }
        } 
        st[x] = 1;
        for(int j=1;j<=n;j++){
            dist[j] = min(dist[j],dist[x] + g[x][j]);
        }
    }
}

int main(){
    cin >> n >> m;
    memset(g,0x3f,sizeof(g));
    for(int i=1;i<=n;i++) g[i][i] = 0;
    for(int i=1;i<=m;i++){
        int a,b,c;
        cin >> a >> b >> c;
        g[a][b] = min(g[a][b],c); 
    }   
    dijkstra();
    for(int i=1;i<=n;i++) cout << dist[i] << endl;
    return 0;
}

0 评论

你确定删除吗?
1024
x

© 2018-2023 AcWing 版权所有  |  京ICP备17053197号-1
用户协议  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标
请输入绑定的邮箱地址
请输入注册信息