冲刺阶段（第5个月）：最短路径算法精讲——迪杰斯特拉与贝尔曼-福德算法

在信息学奥赛CSP-J的备考冲刺阶段，算法进阶是至关重要的一环。今天，我们将深入探讨两种核心的最短路径算法：迪杰斯特拉算法（Dijkstra’s Algorithm）和贝尔曼-福德算法（Bellman-Ford Algorithm）。这两种算法在解决图论问题中具有广泛的应用，掌握它们对于提升算法竞赛成绩具有重要意义。

一、迪杰斯特拉算法（Dijkstra’s Algorithm）

迪杰斯特拉算法是一种用于解决单源最短路径问题的贪心算法，适用于非负权图。其基本思想是从起点出发，每次选择当前距离起点最近的未访问节点，然后更新该节点到其他节点的距离。通过不断迭代，最终得到起点到所有节点的最短路径。

实现步骤：

1. 初始化：将起点到自身的距离设为0，其他节点到起点的距离设为无穷大。
2. 选择当前距离起点最近的未访问节点，标记为已访问。
3. 更新该节点到其他节点的距离，如果通过该节点到达其他节点的距离比已知的距离短，则更新该距离。
4. 重复步骤2和3，直到所有节点都被访问过。

时间复杂度：迪杰斯特拉算法的时间复杂度为O(n^2)，其中n为节点数。在使用优先队列优化后，时间复杂度可降低至O((n+m)logn)，其中m为边数。

二、贝尔曼-福德算法（Bellman-Ford Algorithm）

贝尔曼-福德算法是一种用于解决单源最短路径问题的动态规划算法，适用于带权图，包括负权边。其基本思想是通过多次迭代，逐步逼近最短路径。在每次迭代中，对每条边进行松弛操作，即尝试通过当前边缩短起点到终点的距离。

实现步骤：

1. 初始化：将起点到自身的距离设为0，其他节点到起点的距离设为无穷大。
2. 对图中的每条边进行松弛操作，重复此步骤n-1次，其中n为节点数。
3. 检查是否存在负权回路。如果存在，则说明不存在最短路径；否则，输出起点到各节点的最短路径。

时间复杂度：贝尔曼-福德算法的时间复杂度为O(nm)，其中n为节点数，m为边数。

代码模板：

迪杰斯特拉算法代码模板（使用优先队列优化）：

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

const int INF = 0x3f3f3f3f;
typedef pair<int, int> PII;

vector<vector<PII>> adj; // 邻接表
int dist[1005]; // 距离数组
bool visited[1005]; // 访问标记数组

void dijkstra(int start, int n) {
    memset(dist, INF, sizeof(dist));
    memset(visited, false, sizeof(visited));
    dist[start] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> pq;
    pq.push({0, start});
    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        if (visited[u]) continue;
        visited[u] = true;
        for (auto &edge : adj[u]) {
            int v = edge.first, w = edge.second;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
}

贝尔曼-福德算法代码模板：

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

const int INF = 0x3f3f3f3f;

struct Edge {
    int u, v, w;
};

vector<Edge> edges; // 边集
int dist[1005]; // 距离数组

void bellman_ford(int start, int n, int m) {
    memset(dist, INF, sizeof(dist));
    dist[start] = 0;
    for (int i = 1; i < n; ++i) {
        bool relaxed = false;
        for (int j = 0; j < m; ++j) {
            int u = edges[j].u, v = edges[j].v, w = edges[j].w;
            if (dist[u] != INF && dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                relaxed = true;
            }
        }
        if (!relaxed) break;
    }
    // 检查负权回路
    for (int j = 0; j < m; ++j) {
        int u = edges[j].u, v = edges[j].v, w = edges[j].w;
        if (dist[u] != INF && dist[v] > dist[u] + w) {
            cout << "存在负权回路" << endl;
            return;
        }
    }
}

在备考过程中，建议同学们通过大量练习来熟悉这两种算法的应用场景和实现细节。同时，理解算法的原理和优化方法，有助于在竞赛中灵活运用。

喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！