最短路径

一、单源最短路径

单源最短路径：从源点出发，到其他所有顶点的最短路径。

1.DJ算法(dijkstra)： 适用：权重为非负的图 特点：从源点开始，每次选择当前最短路径已知的顶点扩展，直到所有顶点的最短路径确定。

代码

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

using namespace std;

//存储边的指向和权重
struct Edge {
    int to, weight;
};

//每次将权重大的往前排
struct Compare {
    bool operator()(pair<int, int>& a, pair<int, int>& b) {
        return a.second > b.second;
    }
};

void dijkstra(int start, int n, vector<vector<Edge>>& graph) {
    vector<int> dist(n, INT_MAX);  // 初始化从起点到各个节点的最短距离
    dist[start] = 0;//起点到起点的距离是0

    priority_queue<pair<int, int>, vector<pair<int, int>>, Compare> pq;
    pq.push({start, 0});

    while (!pq.empty()) {
        int u = pq.top().first;//当前点
        int d = pq.top().second;//源点到当前点的距离
        pq.pop();

        if (d > dist[u]) continue;//如果距离小于或等于，进入下一步
				
				//如果距离比已知的小
        for (const auto& edge : graph[u]) {//遍历与当前点相连的所有边
            int v = edge.to;
            int weight = edge.weight;

            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;//更新最短距离
                pq.push({v, dist[v]});
            }
        }
    }

    // 输出最短路径
    for (int i = 0; i < n; i++) {
        if (dist[i] == INT_MAX)
            cout << "INF ";
        else
            cout << dist[i] << " ";
    }
    cout << endl;
}

int main() {
    int n = 5;  // 节点数量
    vector<vector<Edge>> graph(n);

    // 添加边 (u, v, weight)
    graph[0].push_back({1, 10});
    graph[0].push_back({2, 5});
    graph[1].push_back({2, 2});
    graph[1].push_back({3, 1});
    graph[2].push_back({1, 3});
    graph[2].push_back({3, 9});
    graph[3].push_back({4, 4});
    graph[4].push_back({0, 7});
    
    int start = 0;  // 从节点0开始
    dijkstra(start, n, graph);

    return 0;
}

图解

2.SPFA算法： 适用：允许权重为负 特点： 适合稀疏图； 通过不断“松弛”边来更新最短路径，最多迭代v-1次（v是顶点个数）； 可以检测负权环

二、多源最短路径

多源最短路径：从所有顶点出发，到其他所有顶点的最短路径。求的是任意两个点之间的最短路径。因此这个算法每个点都要求，三层循环动态规划。

Floyd-Warshall算法： 适用：适合稠密图，允许负权边（但不允许负权环）。 特点：使用动态规划思想，每次加入一个中间点，更新所有点对之间的最短路径。

代码

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

using namespace std;

void floydWarshall(int n, vector<vector<int>>& dist) {
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX && dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }

    // 输出最短路径
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (dist[i][j] == INT_MAX)
                cout << "INF ";
            else
                cout << dist[i][j] << " ";
        }
        cout << endl;
    }
}

int main() {
    int n = 4;  // 节点数量
    vector<vector<int>> dist(n, vector<int>(n, INT_MAX));

    // 邻接矩阵
    dist[0][0] = 0; dist[0][1] = 3; dist[0][2] = 10; dist[0][3] = INT_MAX;
    dist[1][0] = INT_MAX; dist[1][1] = 0; dist[1][2] = 5; dist[1][3] = 7;
    dist[2][0] = INT_MAX; dist[2][1] = INT_MAX; dist[2][2] = 0; dist[2][3] = 2;
    dist[3][0] = INT_MAX; dist[3][1] = INT_MAX; dist[3][2] = INT_MAX; dist[3][3] = 0;

    floydWarshall(n, dist);

    return 0;
}