Dijkstra

• 适用：单源最短路径问题
• 分类：稠密图用邻接矩阵，稀疏图用邻接表
• 主要步骤：①找到一个离起点最近的点，②用这个点去松弛其它的边

朴素版，处理稠密图（边多）

复杂度；n^2

• 代码

/*
主要步骤：
    1.先找到离起点最近的点t
    2.再使用点t来松弛其它的边
}
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 510, inf = 0x3f3f3f3f3f3f3f3f3f3f3f; //由于使用的是long long,所以正无穷大要开大一些
ll g[N][N], dist[N], n, m;//使用的是邻接矩阵存储,g[x][y]表示x到y的距离为g[x][y],dist[i]表示编号为i的点到起点的距离
bool st[N]; //判断是否在集合s中，集合s表示已经是最短距离的点集

ll dijkstra() {
    memset(dist, inf, sizeof dist);
    dist[1] = 0; //以1号点为起点，距离为0
    for(int i = 1; i <= n; i++) {
        int t = -1; //用t来找当前距离起点最近的点，用t来松弛其他边
        for(int j = 1; j <= n; j++)
            if(!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        st[t] = true;
        for(int j = 1; j <= n; j++)
            dist[j] = min(dist[j], dist[t] + g[t][j]); //松弛操作
    }
    return dist[n] == inf ? -1 : dist[n];
}

int main() {
    cin >> n >> m;
    memset(g, inf, sizeof g);
    while(m--) {
        ll x, y, z; cin >> x >> y >> z;
        g[x][y] = min(g[x][y], z);
    }
    cout << dijkstra() << endl;
    return 0;
}

堆优化版，处理稀疏图（点多）

复杂度；mlogn

• 代码

/*
主要事项：
    - 由于是稀疏图，所以用邻接表来存储，但为了方便书写，这里采用链式前向星来写，关于链式前向星可以参考博客：https://blog.csdn.net/sugarbliss/article/details/86495945
    - 其次，因为我们不仅仅需要知道目前到起点最近的点的距离，也要知道它的编号，所以需要使用pair, 同时，pair是按照第一个元素排列的，我们需要的也是按距离从小到大排序，所以存储的次序不能改变
    - 最后注意使用点对边进行松弛
    - h[i]：结点i的最后一条边的编号为h[i]，初始化为-1
    - dist[i]：结点i到起点的最短距离，初始化为inf
    - next：表示与这个边的起点相同的上一条边的编号
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
const ll N = 1e6 + 10;
const ll inf = 0x3f3f3f3f3f3f3f3f3f3f;
ll h[N], dist[N], vis[N], n, m, cnt;
struct edge {
    ll w, e, next;
}edge[N];
void add(ll x, ll y, ll z) {
    edge[cnt].w = z;
    edge[cnt].e = y;
    edge[cnt].next = h[x];
    h[x] = cnt++;
    return ;
}
ll dijkstra() {
    dist[1] = 0;
    priority_queue<pii, vector<pii>, greater<pii> > heap;
    heap.push({0, 1});
    while(heap.size()) {
        pii t = heap.top(); heap.pop();
        ll point = t.second, distant = t.first;
        if(vis[point]) continue;
        vis[point] = true;
        for(int i = h[point]; i != -1; i = edge[i].next) {
            int j = edge[i].e;
            if(dist[j] > edge[i].w + distant) {
                dist[j] = edge[i].w + distant;
                heap.push({dist[j], j});
            }
        }
    }
    return dist[n] == inf ? -1 : dist[n];
}
int main() {
    scanf("%lld %lld", &n, &m);
    memset(h, -1, sizeof h);
    memset(dist, inf, sizeof dist);
    while(m--) {
        ll x, y, z; scanf("%lld %lld %lld", &x, &y, &z);
        add(x, y, z);
    }
    cout << dijkstra() << endl;
    return 0;
}