单源最短路径问题与Dijkstra算法

单源最短路径问题（Single Source Shortest Path, SSSP）

是图论中的一个经典问题。它的目标是在一个加权图中，找到给定的起点（源点）到图中所有其他节点的最短路径。

问题定义：

图：图可以是有向图或无向图，通常包含若干个节点和边，每条边都有一个非负权重（即从一个节点到另一个节点的代价或距离）。
起点（源点）：单源最短路径问题会指定一个起始节点，称为源节点，问题要求从这个源节点出发，计算它到图中其他所有节点的最短路径。
最短路径：最短路径是指从源节点到目标节点经过的路径中，总边权重之和最小的路径。

具体目标：

对于给定的源节点s，你需要找到从s到每个其他节点v的最短路径长度，并且路径上的权重和最小。

常见的算法：

Dijkstra算法：
- 解决边权非负的单源最短路径问题，时间复杂度为$O((V + E) \log V)$，适合稀疏图。
Bellman-Ford算法：
- 可以处理负权边的情况，且能够检测负权环，时间复杂度为$O(V \times E)$。
Floyd-Warshall算法：
- 这是一个多源最短路径算法，可以计算图中任意两个节点之间的最短路径，时间复杂度为O(V^3)。
SPFA算法（Shortest Path Faster Algorithm）：
- Bellman-Ford的优化版本，通常在图较稀疏时运行更快。

Dijkstra算法：

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

// 定义一个结构体来表示边
struct Edge {
    int to;     // 边的目标节点
    int weight; // 边的权重
};

// 定义一个pair来表示优先队列中的元素，first为当前距离，second为当前节点
using pii = pair<int, int>;

// Dijkstra算法函数，参数为起点和图的邻接表
vector<int> dijkstra(int start, const vector<vector<Edge>>& graph) {
    int n = graph.size();  // 获取图中节点的数量
    vector<int> dist(n, INT_MAX);  // 初始化每个节点的距离为无穷大
    dist[start] = 0;  // 起点到自身的距离为0

    // 定义优先队列，按照距离升序排列，pair的格式是{距离, 节点}
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({0, start});  // 将起点放入优先队列

    // 当优先队列不为空时，执行以下操作
    while (!pq.empty()) {
        int curr_dist = pq.top().first;  // 获取当前节点的距离
        int curr_node = pq.top().second;  // 获取当前节点
        pq.pop();  // 弹出队首元素

        // 如果当前距离已经大于记录的最短距离，跳过（优化）
        if (curr_dist > dist[curr_node]) continue;

        // 遍历当前节点的邻居
        for (const Edge& edge : graph[curr_node]) {
            int next_node = edge.to;        // 邻居节点
            int weight = edge.weight;       // 边的权重

            // 计算从当前节点到邻居节点的距离
            if (dist[curr_node] + weight < dist[next_node]) {
                dist[next_node] = dist[curr_node] + weight;  // 更新邻居节点的最短距离
                pq.push({dist[next_node], next_node});  // 将邻居节点加入优先队列
            }
        }
    }

    return dist;  // 返回从起点到其他所有节点的最短距离
}

int main() {
    int n, m;  // n为节点数，m为边数
    cout << "输入图的节点数和边数：";
    cin >> n >> m;

    // 定义图的邻接表
    vector<vector<Edge>> graph(n);

    cout << "输入每条边（格式：起点 终点 权重）：\n";
    for (int i = 0; i < m; ++i) {
        int u, v, w;  // u为起点，v为终点，w为权重
        cin >> u >> v >> w;
        graph[u].push_back({v, w});  // 添加从u到v的边，权重为w
        // 如果是无向图，需要加上这行代码：
        // graph[v].push_back({u, w});  // 添加从v到u的边
    }

    int start;  // 起点
    cout << "输入起点：";
    cin >> start;

    // 执行Dijkstra算法
    vector<int> dist = dijkstra(start, graph);

    // 输出结果
    cout << "从起点到其他节点的最短距离：" << endl;
    for (int i = 0; i < n; ++i) {
        if (dist[i] == INT_MAX)
            cout << "节点 " << i << " 不可达" << endl;  // 如果距离为无穷大，说明不可达
        else
            cout << "到节点 " << i << " 的最短距离为： " << dist[i] << endl;  // 输出最短距离
    }

    return 0;  // 程序结束
}

图的描述

节点: 0, 1, 2, 3, 4
边及其权重：
- 0 → 1 (权重 1)
- 0 → 2 (权重 4)
- 1 → 2 (权重 2)
- 1 → 3 (权重 5)
- 2 → 3 (权重 3)
- 3 → 4 (权重 1)

目标

我们将从节点 0 开始，使用Dijkstra算法计算到其他节点的最短路径。

初始化

距离数组 dist[]：初始化为无穷大，源节点的距离为0。
- dist[0] = 0
- dist[1] = ∞
- dist[2] = ∞
- dist[3] = ∞
- dist[4] = ∞
优先队列：将源节点加入优先队列。
- pq = [(0, 0)]（表示距离为0，节点为0）

执行过程

处理节点 0：
- 从优先队列中取出 (0, 0)。
- 遍历邻居节点：
  - 对于 1，更新距离：
    - dist[1] = min(∞, 0 + 1) = 1
    - 加入优先队列：pq = [(1, 1)]
  - 对于 2，更新距离：
    - dist[2] = min(∞, 0 + 4) = 4
    - 加入优先队列：pq = [(1, 1), (4, 2)]
处理节点 1：
- 从优先队列中取出 (1, 1)。
- 遍历邻居节点：
  - 对于 2，更新距离：
    - dist[2] = min(4, 1 + 2) = 3
    - 更新优先队列：pq = [(3, 2), (4, 2)]（会自动调整优先队列顺序）
  - 对于 3，更新距离：
    - dist[3] = min(∞, 1 + 5) = 6
    - 加入优先队列：pq = [(3, 2), (4, 2), (6, 3)]
处理节点 2：
- 从优先队列中取出 (3, 2)。
- 遍历邻居节点：
  - 对于 3，更新距离：
    - dist[3] = min(6, 3 + 3) = 6（不变）
  - 这个节点不更新，不加入队列。
处理节点 3：
- 从优先队列中取出 (6, 3)。
- 遍历邻居节点：
  - 对于 4，更新距离：
    - dist[4] = min(∞, 6 + 1) = 7
    - 加入优先队列：pq = [(7, 4)]
处理节点 4：
- 从优先队列中取出 (7, 4)。
- 节点 4 没有邻居节点，不再更新。

最终结果

dist[0] = 0 (到自身)
dist[1] = 1 (通过边 0 → 1)
dist[2] = 3 (通过边 0 → 1 → 2)
dist[3] = 6 (通过边 0 → 1 → 2 → 3)
dist[4] = 7 (通过边 0 → 1 → 2 → 3 → 4)

对于一次性获得所有路径间的最小路径（包括负权）,可以用floyd算法

下面是Floyd-Warshall算法的C++实现。该实现使用一个二维数组来表示图的邻接矩阵，并通过三重循环来更新所有节点对之间的最短路径。

Floyd-Warshall C++ 实现

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

// 定义无穷大，表示节点之间不可达
const int INF = 1e9;

// Floyd-Warshall算法实现
void floydWarshall(vector<vector<int>>& graph, int n) {
    // 初始化距离矩阵
    vector<vector<int>> dist = graph;

    // 三重循环，逐个更新通过每个中间节点的路径
    for (int k = 0; k < n; ++k) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                // 更新dist[i][j]，如果通过k节点可以缩短路径
                if (dist[i][k] < INF && dist[k][j] < INF) {
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }

    // 输出最终的最短路径矩阵
    cout << "The following matrix shows the shortest distances between every pair of vertices:" << endl;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (dist[i][j] == INF)
                cout << "INF" << " ";
            else
                cout << dist[i][j] << "   ";
        }
        cout << endl;
    }
}

int main() {
    int n = 5; // 节点数量
    // 邻接矩阵表示的图
    vector<vector<int>> graph = {
        {0, 1, 4, INF, INF},
        {INF, 0, 2, 5, INF},
        {INF, INF, 0, 3, INF},
        {INF, INF, INF, 0, 1},
        {INF, INF, INF, INF, 0}
    };

    // 执行Floyd-Warshall算法
    floydWarshall(graph, n);

    return 0;
}

代码说明

初始化：
- INF 定义为一个非常大的数，用于表示节点之间不可达。这里用 1e9 (即 $10^9$) 来表示。
- graph 是一个二维数组，表示图的邻接矩阵。
核心算法：
- 三重循环遍历所有节点 k，i 和 j，其中 k 是中间节点。检查是否通过 k 作为中间节点可以使 i 到 j 的路径更短。
- 如果通过节点 k 可以使 dist[i][j] 更短，那么就更新 dist[i][j]。
- dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); 这就是动态规划的更新公式。
输出结果：
- 最终 dist 数组中保存了所有节点对之间的最短距离。
- 如果节点对不可达，显示 INF。

示例输出

对于上面的代码，输出将是：

The following matrix shows the shortest distances between every pair of vertices:
0   1   3   6   7   
INF 0   2   5   6   
INF INF 0   3   4   
INF INF INF 0   1   
INF INF INF INF 0