首页 > 编程笔记 > C++笔记 阅读：4

Dijkstra算法详解（C++实现，附带示例）

Dijkstra 算法是一种用于解决不含负权环的单源最短路径问题的贪心算法。它可以在带权重的有向图或无向图中找到从一个起始顶点到所有其他顶点的最短路径。

Dijkstra 算法的基本思想是通过逐步拓展当前已知的最短路径来逐步找到最终的最短路径。具体来说，该算法执行以下步骤：
  1. 初始化：将起始顶点标记为已访问，并将距离设置为 0。将所有其他顶点的距离设置为无穷大（或一个足够大的数）。
  2. 更新距离：对于起始顶点的所有邻接点，更新它们的距离。具体来说，如果通过访问起始顶点可以缩短到达某个邻居的距离，则更新该邻居的距离。
  3. 选择下一个顶点：从尚未访问的顶点中选择一个具有最小距离的顶点。这样可以保证选择的顶点是当前已知距离最小的。
  4. 标记为已访问：将选定的顶点标记为已访问，这样就不会再次访问它。
  5. 重复：重复步骤 2 到 4，直到所有顶点都被访问过或没有可访问的顶点为止。
  6. 结束：算法结束后，每个顶点的最短路径都得到了计算。

接下来，我们将通过一个实例来深入理解 Dijkstra 算法。

【实例】给定一个包含 n 个顶点、m 条边的有向图，要求计算出顶点 1 到顶点 n 的最短距离。可能存在重边和自环。
输入格式：
输出格式：
一个整数，表示顶点 1 到顶点 n 的最短距离；若不存在从顶点 1 到顶点 n 的路径，则输出 −1。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 2e5 + 9;
const ll inf = 2e18;                // 注意 inf 不要开得非常大，要确保 2*inf 也不会溢出
int n, m;                           // 放在全局方便使用

struct Edge {
    // x 为顶点编号，w 为到该顶点的距离（权重）
    ll x, w;
    // 这样写，让 w 小的在堆顶
    bool operator<(const Edge &u) const {
        return w != u.w ? w > u.w : x < u.x;
    }
};

vector<Edge> g[N];
ll d[N];                            // d[i] 表示从顶点 1 到顶点 i 的最短距离

void dijkstra(int st) {
    // 初始化 d 数组为无穷大
    // 推荐大家直接写这种 for 循环写法，不容易出错
    for (int i = 1; i <= n; ++i) d[i] = inf;
    priority_queue<Edge> pq;        // 堆中的排序规则由 Edge 小于号决定
    bitset<N> vis;                  // vis[i] == true 表示已经拓展过 i，即得到了顶点 1 到顶点 i 的最短距离
    pq.push({st, d[st] = 0});
    while (pq.size()) {
        int x = pq.top().x; pq.pop();
        if (vis[x]) continue;       // 如果已经拓展过，则直接跳过
        vis[x] = true;
        for (const auto &e : g[x]) {
              int y = e.x;
              ll  w = e.w;
              if (d[x] + w < d[y]) {
                  d[y] = d[x] + w;
                  pq.push({y, d[y]});
              }
          }
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        ll x, y, w; cin >> x >> y >> w;
        g[x].push_back({y, w});
    }
    dijkstra(1);                    // 从顶点 1 出发求“单源最短路径”，结果保存在 d 数组中
    cout << (d[n] == inf ? -1 : d[n]) << '\n';
    return 0;
}
样例输入：

3 3
1 2 5
2 3 2
1 3 10

样例输出：

7

为什么Dijkstra算法无法处理负权图

Dijkstra 算法的一个重要特性是它只能应用于没有负权边的图。这是因为在更新距离时，Dijkstra 算法假设较短的路径是优先选择的。如果存在负权边，则可能会导致算法出现错误。

Dijkstra 算法不能用于包含负权边的图的原因如下：

1) 违背基本原理

Dijkstra 算法的基本原理是“贪心”，它每次选择当前距离最短的顶点，并假设该顶点的最短距离已经被确定，然后更新与该顶点相邻的顶点的距离。

如果图中存在负权边，那么即使某个顶点的最短距离已经被确定，由于负权边的存在，后续仍有可能找到一条更短的路径到达该顶点，这违背了 Dijkstra 算法的基本原理。

2) 可能导致无限循环

在包含负权环的图中，Dijkstra 算法可能会陷入无限循环。因为每次经过负权环，都可以得到一个更短的路径，这意味着算法永远不会收敛。

3) 不保证正确性

即使图中没有负权环，但只要存在负权边，Dijkstra 算法也不能保证找到正确的最短路径。因为算法在确定某个顶点的最短距离时，并没有考虑到后续可能存在的负权边，这可能导致算法得到的结果是不正确的。

如果需要在包含负权边的图中找到最短路径，则可以使用其他算法，如 Bellman−Ford 算法，它可以处理负权边，而且能够检测图中是否存在负权环。但遗憾的是其时间复杂度较高。如果需要更好的时间复杂度，则可以考虑使用 Johnson 算法。

相关文章