迪杰斯特拉算法及其优化

今天又重新复习了一遍迪杰斯特拉算法，或者说叫重新学了一遍（淦）

然后顺便补了一下以前的博客

迪杰斯特拉算法是一种用来计算最短路的算法，要求是路径的长度必须是正值（正权值）

算法图解：

图源：OSCHINA， 侵删

例题：

洛谷P3371或者洛谷P4779

AC代码：

/*
* ===============================================
* Filename: djs_c.cpp
* Description: 迪杰斯特拉未优化版
* Website: https://grimoire.cn
* Copyright (c) 2020 Mr.Sen. All rights reserved.
* ===============================================
*/

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
const int INF = 2147483647;
int a[N];

struct edge 
{
    int to;
    int cost;
};

vector <edge> g[N];
int d[N];
int vis[N];
int n;

int djs(int s)
{
    int min1, k;
    for (int i = 1; i <= n; i++) d[i] = INF;
    
    d[s] = 0;
    for (int i = 1; i < n; i++)
    {
        min1 = INF;
        k = s;
        for (int j = 1; j <= n ;j++)
        {
            if (vis[j] == 0 && min1 > d[j])
            {
                min1 = d[j];
                k = j;
            }
        }
        vis[k] = 1;
        for (int j = 0; j < g[k].size(); j++)
        {
            int to = g[k][j].to;
            if (vis[to] == 0 && min1 + g[k][j].cost < d[to])
            {
                d[to] = min1 + g[k][j].cost;
            }
        }
    }
    return 0;
}

int main()
{
    int m, s, x;
    cin >> n >> m >> s;
    edge tmp;
    for (int i = 1; i <= m; i++)
    {
        cin >> x >> tmp.to >> tmp.cost;
        g[x].push_back(tmp);
    }
    djs(s);
    for (int i = 1; i <= n; i++)
    {
        cout << d[i] << " ";
    }
    return 0;
}

/*
* ===============================================
* Filename: djs_dui.cpp
* Description: 迪杰斯特拉堆优化版
* Website: https://grimoire.cn
* Copyright (c) 2020 Mr.Sen. All rights reserved.
* ===============================================
*/

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
vector<int> d[MAXN];
vector<int> e[MAXN];
long long dis[MAXN];
bool vis[MAXN];
int n, m;
priority_queue<pair<int, int> > q;

void dj(int s)
{
    int temp, y, z;
    memset(vis, 0, sizeof(vis));
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0; 
    q.push(make_pair(0, s));
    while (!q.empty())
    {
        temp = q.top().second;
        q.pop();
        if (vis[temp])
            continue;
        vis[temp] = 1;
        for (int i = 0; i < d[temp].size(); i++)
        {
            y = d[temp][i];
            z = e[temp][i];
            if (dis[y] > dis[temp] + z)
            {
                dis[y] = dis[temp] + z;
                q.push(make_pair(-dis[y], y));
            }
        }
    }
}
int main()
{
    int x, y, z, ans = 0,s;
    cin >> n >> m >> s;
    for (int i = 1; i <= m; i++)
    {
        cin >> x >> y >> z;
        d[x].push_back(y);
        e[x].push_back(z);
    }
    dj(s);
    for (int i = 1; i <= n; i++)
        cout << dis[i] << " ";
    return 0;
}