dj普通版本

存储图的关系用邻接表 伪代码：

int dist[n],state[n];
dist[1] = 0, state[1] = 1;
for(i:1 ~ n)
{
    t <- 没有确定最短路径的节点中距离源点最近的点;
    state[t] = 1;
    更新 dist;
}

时间复杂度分析

O(n^2)

#include<iostream>
#include<cstring>
#include<algorithm>

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

int dijkstra(){

    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    //st[1] = true;//不能去赋值哦否则就挂了，因为后面要用节点1去更新其他节点
    //更新n次
    for(int i=0; i<n; i++){
        int t  = -1;//找最小值
        for(int j=1; j<=n; j++){
            if(!st[j] && (t==-1||dist[t]>dist[j]) ){
                t = j; //找到最小值  
            }
        }

        st[t] = true;

        //用最小值t更新所有的未更新的节点
        for(int j=1; j<=n; j++){
            dist[j] = min(dist[j], dist[t]+g[t][j]);
        }

    }


    if(dist[n]==0x3f3f3f3f) dist[n] =-1;
    return dist[n];

}

int main(){
    scanf("%d%d",&n,&m);
    memset(g, 0x3f, sizeof g);
    for(int i=1; i<=m; i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        g[a][b] = min(g[a][b], c);

    }

    int t = dijkstra();
    printf("%d\n", t);

    return 0;
}

堆优化版dijkstra适合稀疏图

思路

堆优化版的dijkstra是对朴素版dijkstra进行了优化，在朴素版dijkstra中时间复杂度最高的寻找距离 最短的点O(n^2)可以使用最小堆优化。 1. 一号点的距离初始化为零，其他点初始化成无穷大。 2. 将一号点放入堆中。 3. 不断循环，直到堆空。每一次循环中执行的操作为： 弹出堆顶（与朴素版diijkstra找到S外距离最短的点相同，并标记该点的最短路径已经确定）。 用该点更新临界点的距离，若更新成功就加入到堆中。

时间复杂度分析

时间复杂度 O(mlogn) 每次找到最小距离的点沿着边更新其他的点，若dist[j] > distance + w[i]，表示可以更新dist[j]，更新后再把j点和对应的距离放入小根堆中。由于点的个数是n，边的个数是m，在极限情况下（稠密图m=n(n−1)/2) 最多可以更新m回，每一回最多可以更新n个点（严格上是n - 1个点），有m回，因此最多可以把n^2个点放入到小根堆中，因此每一次更新小根堆排序的情况是O(log(n^2))，一共最多m次更新，因此总的时间复杂度上限是O(mlog((n^2)))=O(2mlogn)=O(mlogn)

#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

typedef pair<int, int> PII;
#define x first
#define y second
const int N = 1e6 + 10 , INF = 0x3f3f3f3f;

int n, m;
int dist[N];
bool st[N];
vector<PII> g[N];  // 邻接表，存储图的边

int dijkstra() {
    memset(dist, 0x3f, sizeof dist);  // 初始化距离数组，所有点初始距离为INF
    dist[1] = 0;  // 起点1到自己的距离为0
    priority_queue<PII, vector<PII>, greater<PII>> heap;  // 最小堆，维护距离最小的点
    heap.push({0, 1});  // 将起点1加入堆，距离为0

    while (!heap.empty()) {
        auto t = heap.top();
        heap.pop();

        int u = t.y, w = t.x;

        // 如果当前点的距离不是最新的，跳过
        if (st[u]) continue;
        st[u] = true;

        // 遍历u的所有邻边，尝试松弛
        for (auto v : g[u]) {
            int ver = v.x, cost = v.y;
            // 如果通过u到达v更优，更新距离并将v加入堆
            if (dist[u] + cost < dist[ver]) {
                dist[ver] = dist[u] + cost;
                heap.push({dist[ver], ver});
            }
        }
    }

    // 如果目标点n的距离依然为INF，说明不可达
    if (dist[n] == INF) return -1;
    return dist[n];
}

int main() {
    scanf("%d%d", &n, &m);
    while (m--) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        g[a].push_back({b, c});
    }

    int result = dijkstra();
    printf("%d\n", result);

    return 0;
}

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com