详解Dijkstra算法原理及其C++实现

前言

Dijkstra算法是一种常见的求解单源最短路径的算法，本文将对其进行详细的讲解。

原理

Dijkstra算法的核心思想是贪心，即每次都选择当前最短路径上距离起点最近的顶点，并通过该顶点更新与其相邻的顶点的距离。Dijkstra算法使用一个数组dist[i]来记录起点到每个顶点的最短距离，同时使用一个visited[i]数组来记录每个顶点是否被访问过。

具体步骤可概括为：

1. 初始化：将起点s加入集合S，将起点到每个顶点的距离dist[i]初始化为无穷大，将visited[i]初始化为false。
2. 更新：从集合V-S中选择距离起点s最近的顶点u，将u加入集合S，对于与u相邻的顶点v，若dist[u]+w(u,v)<dist[v]，则更新dist[v]=dist[u]+w(u,v)，其中w(u,v)表示边(u,v)的权值。
3. 重复进行步骤2，直到所有顶点都被加入集合S。

Dijkstra算法的时间复杂度为O(n^2)，但可以通过堆优化的方式将其优化到O(nlogn)。

C++实现

以下是Dijkstra算法的C++实现代码：

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

const int MAXN = 1005;
const int INF = 0x3f3f3f3f;

int dist[MAXN], visited[MAXN];
vector<pair<int, int>> G[MAXN];

void Dijkstra(int s) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    memset(dist, INF, sizeof(dist));
    dist[s] = 0;
    q.push({0, s});

    while (!q.empty()) {
        int u = q.top().second;
        q.pop();
        if (visited[u]) continue;
        visited[u] = 1;
        for (auto& v : G[u]) {
            int d = v.second;
            if (dist[v.first] > dist[u] + d) {
                dist[v.first] = dist[u] + d;
                if (!visited[v.first]) q.push({dist[v.first], v.first});
            }
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;

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

    int s;
    cin >> s;
    Dijkstra(s);

    for (int i = 1; i <= n; i++) {
        if (dist[i] == INF) cout << "INF" << endl;
        else cout << dist[i] << endl;
    }

    return 0;
}

示例说明

示例1

输入：

5 6
1 2 10
1 3 5
2 4 1
3 4 2
3 5 1
4 5 4
1

输出：

0
5
7
6
10

解释：

该图如下所示：

1 --10-- 2
|\     /
| 5\  /1
|   \/
|   /\
|2/   \4
v/     \
3 --2-- 5

起点为1，最短路径如下：

• 1->2: 10
• 1->3: 5
• 1->4->2: 11
• 1->4->3: 7
• 1->4->5: 10

因此，输出结果为0 5 7 11 10。

示例2

输入：

4 4
1 2 3
1 3 5
2 4 4
3 4 2
1

输出：

0
3
5
7

解释：

该图如下所示：

1 --3-- 2
|\     /
| 5\  /4
|   \/
|   /\
|2/   \4
v/     \
3 --2-- 4

起点为1，最短路径如下：

• 1->2: 3
• 1->3: 5
• 1->2->4: 7
• 1->3->4: 7

因此，输出结果为0 3 5 7。