此文章的MarkDown、源码以及原图：点击跳转Gitee仓库

这篇博客将会解释单点最短路算法(Djikstra算法)以及相应的数据结构。

数据输入与输出

此文章的MarkDown、源码以及原图：

输入三个整数n,m,k，分别代表图中一共有n个点，m条边，起点为k。

输出一个n行，分别代表起点k到各个点的最短距离。特殊的，如果某些点与起点不在同一个并查集内，距离可记为无限大(INF)，大小定义为0x3f3f3f3f。

无限大定义：

1
#define INF 0x3f3f3f3f

输出示例：

1
2
3
4
for (int i=0;i<dist.size();i++) {
        if (dist[i]==INF) cout<<"dist["<<i<<"]= INF"<<endl;
        else cout<<"dist["<<i<<"]= "<<dist[i]<<endl;
    }

算法解释

Dijkstra 算法是一种用于在加权图中找到从起点到所有其他节点的最短路径的贪心算法——它每次都优先处理当前已知距离最短的节点，逐步向外扩展，直到确定所有可达节点的最短距离。

算法手记：

1

2

3

数据结构

定义邻接表元素：

1
2
3
struct Edge {
    int u,v,w;//  u->v,长度为w
};

小根堆元素：

1
2
3
4
5
6
7
struct Node {
    int v,dist;// 起点到v点的dist距离

    bool operator<(const Node &n) const {
        return dist > n.dist;//所有边按照长度递增排序
    }
};

容器定义：

1
2
3
4
vector<vector<Edge>> cur(n);    // 定义邻接表
vector<int>dist(n,INF); // 从起点到各个点的最短距离
vector<bool>inS(n,0);   // 判断此点是否在确定的最短路中
priority_queue<Node>pq;      // 小根堆，用于每次更新最小的新边到最短路中

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
//
// Created by AKKO on 2026/4/22.
//
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f

struct Edge {
    int u,v,w;//  u->v,长度为w
};

struct Node {
    int v,dist;// 起点到v点的dist距离

    bool operator<(const Node &n) const {
        return dist > n.dist;
    }
};

int main() {
    int n,m,k;cin>>n>>m>>k; // n个点  m条边  k为起点

    vector<vector<Edge>> cur(n);    // 定义邻接表
    vector<int>dist(n,INF); // 从起点到各个点的最短距离
    vector<bool>inS(n,0);   // 判断此点是否在确定的最短路中
    priority_queue<Node>pq;      // 小根堆，用于每次更新最小的新边到最短路中

    dist[k]=0; // 起点距离为0

    for (int i=0;i<m;i++) {
        int u,v,w;cin>>u>>v>>w;
        cur[u].push_back({u,v,w});
    }

    pq.push({k,dist[k]});

    while (!pq.empty()) {
        Node node=pq.top();         // 每次取长度最短的路尝试加入最短路
        pq.pop();
        int u=node.v;
        if (inS[u]) continue;  // 此点已在最短路中，需跳过
        inS[u]=1;              // 不在就加入
        for (Edge e:cur[u]) {
            int v=e.v;
            int w=e.w;
            if (dist[v]>dist[u]+w) {
                dist[v]=dist[u]+w;
                pq.push({v,dist[v]});
            }
        }
    }

    for (int i=0;i<dist.size();i++) {
        if (dist[i]==INF) cout<<"dist["<<i<<"]= INF"<<endl;
        else cout<<"dist["<<i<<"]= "<<dist[i]<<endl;
    }
    return 0;
}

/*
input:
6 11 0
0 1 50
0 2 10
0 4 70
1 2 15
1 4 10
2 0 20
2 3 15
3 1 20
3 4 35
4 3 30
5 3 3

output:
dist[0]= 0
dist[1]= 45
dist[2]= 10
dist[3]= 25
dist[4]= 55
dist[5]= INF
*/

其他的事

我会继续练习在 Typora 中写 MarkDown 的能力，并且我会偶尔更新我的生活或学习博客。我真的很希望能和大家交朋友~

这是我的 B站频道
这是我的 Gitee

我的算法与工程代码会同步更新哦，请给我点个Star吧~

呆唯思考