Obsidian-Knowledge-Base/X-Knowledge-Base/raw/Joplin/计算机专业基础/数据结构与算法/16.图-最短路径.md

16. 图-最短路径

概念

最短路径：在一个带权图中，从某顶点出发到另一顶点，各条边上权值之和最小的那条路径。分两类问题：

• 单源最短路径：求一个源点到其余所有顶点的最短路径。最经典的是 Dijkstra（迪杰斯特拉）算法。
• 多源最短路径：求任意两点之间的最短路径。最经典的是 Floyd（弗洛伊德）算法。

Dijkstra 算法（贪心）：把顶点分成"已确定最短距离"和"未确定"两组。每轮从未确定的顶点中选出距离源点最近的一个，把它加入已确定组（贪心选择），然后用它松弛（relax）所有未确定邻点：若 dist[u] + w(u,v) < dist[v]，就更新 dist[v]。由于每轮选出的顶点距离已最小，且所有边权非负，因此它一旦确定就不会再变。

为什么 Dijkstra 不能处理负权边？ 贪心假设"已确定的顶点距离不会再变小"。但若存在负权边，一条"更长"的路径可能通过负权边把某个已确定顶点的距离变得更小，从而推翻前面的决定。因此 Dijkstra 只适用于无负权边的图；有负权边应改用 Bellman-Ford，有负环则无解。

Floyd 算法（动态规划）：用二维数组 d[i][j] 记录 i 到 j 当前最短距离，初始为边权或 ∞。核心是三重循环枚举中间点 k：

d[i][j] = min(d[i][j], d[i][k] + d[k][j])

每引入一个中间点 k，就尝试让所有点对经过 k 中转是否更短。循环完所有 k 后，d[i][j] 即为 i 到 j 的最短距离。它允许负权边，但图中不能有负权环。

区别：Dijkstra 单源、贪心、O(n²)（可优化）；Floyd 多源、动态规划、O(n³)，适合顶点较少的稠密图。

核心操作 / 算法

Dijkstra（邻接矩阵，O(n²)）：

1. 初始化：dist[s]=0，其余 dist=∞，visited 全 false；parent 记录路径。
2. 重复 n 次： a. 在未访问顶点中选 dist 最小者 u，标记访问（距离确定）； b. 对每个未访问邻点 v：若 dist[u]+w(u,v) < dist[v]，更新 dist[v] 并记 parent[v]=u。
3. 结束后 dist[i] 为 s 到 i 的最短距离，沿 parent 回溯可得最短路径。

Floyd（O(n³)）：

1. 初始化 d = 邻接矩阵（无边记 ∞，对角线 0）。
2. for k in 0..n-1（中间点）：for i for j：d[i][j] = min(d[i][j], d[i][k] + d[k][j])。
3. 结束后 d[i][j] 即任意两点最短距离。

复杂度分析

算法	时间复杂度	空间复杂度	说明
Dijkstra（邻接矩阵）	O(n²)	O(n)	每轮 O(n) 扫描选最小
Dijkstra（堆/优先队列优化）	O((n+e)·log n)	O(n+e)	用堆取最小，每条边至多一次堆更新
Floyd	O(n³)	O(n²)	三重循环 + n×n 距离矩阵

为什么：

• Dijkstra 共确定 n 个顶点，每轮用 O(n) 扫描未访问顶点找最小 dist，加上 O(n) 松弛，共 O(n²)。堆优化后取最小 O(log n)，边全部入堆/更新累计 O((n+e)·log n)。
• Floyd 枚举中间点 k（n 次）× 起点 i（n 次）× 终点 j（n 次），共 O(n³)；需要保存 n×n 的距离矩阵，空间 O(n²)。

语言实现

下面 4 种语言的实现演示相同的操作：对同一个有向带权图（5 个顶点、9 条边），运行 Dijkstra 求从顶点 0 到各点的最短距离与路径，并运行 Floyd 输出任意两点间最短距离矩阵。

C

#include <stdio.h>

#define MAX 20
#define INF 1000000000

int n;
int graph[MAX][MAX];      // 有向带权图邻接矩阵

// Dijkstra：单源最短路径（贪心，邻接矩阵，O(n^2)，不能有负权）
void dijkstra(int src) {
    int dist[MAX], parent[MAX], visited[MAX];
    for (int i = 0; i < n; i++) {
        dist[i] = INF;
        parent[i] = -1;
        visited[i] = 0;
    }
    dist[src] = 0;
    for (int k = 0; k < n; k++) {
        // 选未访问且距离最小的顶点
        int u = -1, min = INF;
        for (int i = 0; i < n; i++)
            if (!visited[i] && dist[i] < min) { min = dist[i]; u = i; }
        if (u == -1) break;             // 剩余顶点不可达
        visited[u] = 1;
        // 松弛：用 u 更新邻点距离
        for (int v = 0; v < n; v++)
            if (!visited[v] && graph[u][v] != INF && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
                parent[v] = u;
            }
    }
    // 输出距离与路径
    for (int i = 0; i < n; i++) {
        if (i == src) continue;
        if (dist[i] >= INF) {
            printf("%d -> %d: 不可达\n", src, i);
            continue;
        }
        // 沿 parent 回溯路径
        int path[MAX], len = 0;
        for (int cur = i; cur != -1; cur = parent[cur])
            path[len++] = cur;
        printf("%d -> %d: 距离=%d 路径=", src, i, dist[i]);
        for (int j = len - 1; j >= 0; j--) {
            if (j < len - 1) printf(" -> ");
            printf("%d", path[j]);
        }
        printf("\n");
    }
}

// Floyd：多源最短路径（动态规划，O(n^3)）
void floyd() {
    int d[MAX][MAX];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            d[i][j] = graph[i][j];

    for (int k = 0; k < n; k++)          // 枚举中间点
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (d[i][k] != INF && d[k][j] != INF
                    && d[i][k] + d[k][j] < d[i][j])
                    d[i][j] = d[i][k] + d[k][j];

    printf("Floyd 任意两点最短距离矩阵:\n");
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (d[i][j] >= INF) printf("%5s", "INF");
            else printf("%5d", d[i][j]);
        }
        printf("\n");
    }
}

int main() {
    n = 5;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            graph[i][j] = (i == j) ? 0 : INF;

    // 有向带权图的边 (u, v, w)
    int raw[][3] = {{0,1,10},{0,3,5},{1,2,1},{1,3,2},
                    {3,1,3},{3,2,9},{3,4,2},{2,4,4},{4,2,6}};
    for (int i = 0; i < 9; i++)
        graph[raw[i][0]][raw[i][1]] = raw[i][2];

    printf("=== Dijkstra (from 0) ===\n");
    dijkstra(0);
    printf("\n=== Floyd ===\n");
    floyd();
    return 0;
}

C++

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

const int INF = 1000000000;

// Dijkstra：单源最短路径（贪心，邻接矩阵，O(n^2)，不能有负权）
void dijkstra(const vector<vector<int>>& g, int n, int src) {
    vector<int> dist(n, INF), parent(n, -1);
    vector<bool> visited(n, false);
    dist[src] = 0;
    for (int k = 0; k < n; k++) {
        // 选未访问且距离最小的顶点
        int u = -1;
        for (int i = 0; i < n; i++)
            if (!visited[i] && (u == -1 || dist[i] < dist[u])) u = i;
        if (u == -1 || dist[u] >= INF) break;   // 剩余顶点不可达
        visited[u] = true;
        // 松弛：用 u 更新邻点距离
        for (int v = 0; v < n; v++)
            if (!visited[v] && g[u][v] < INF && dist[u] + g[u][v] < dist[v]) {
                dist[v] = dist[u] + g[u][v];
                parent[v] = u;
            }
    }
    // 输出距离与路径
    for (int i = 0; i < n; i++) {
        if (i == src) continue;
        if (dist[i] >= INF) { cout << src << " -> " << i << ": 不可达\n"; continue; }
        vector<int> path;
        for (int cur = i; cur != -1; cur = parent[cur]) path.push_back(cur);
        cout << src << " -> " << i << ": 距离=" << dist[i] << " 路径=";
        for (int j = (int)path.size() - 1; j >= 0; j--) {
            if (j != (int)path.size() - 1) cout << " -> ";
            cout << path[j];
        }
        cout << "\n";
    }
}

// Floyd：多源最短路径（动态规划，O(n^3)）
void floyd(const vector<vector<int>>& g, int n) {
    vector<vector<int>> d = g;
    for (int k = 0; k < n; k++)          // 枚举中间点
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (d[i][k] + d[k][j] < d[i][j])
                    d[i][j] = d[i][k] + d[k][j];

    cout << "Floyd 任意两点最短距离矩阵:\n";
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (d[i][j] >= INF) cout << setw(5) << "INF";
            else cout << setw(5) << d[i][j];
        }
        cout << "\n";
    }
}

int main() {
    int n = 5;
    vector<vector<int>> g(n, vector<int>(n, INF));
    for (int i = 0; i < n; i++) g[i][i] = 0;

    // 有向带权图的边 (u, v, w)
    int raw[][3] = {{0,1,10},{0,3,5},{1,2,1},{1,3,2},
                    {3,1,3},{3,2,9},{3,4,2},{2,4,4},{4,2,6}};
    for (int i = 0; i < 9; i++)
        g[raw[i][0]][raw[i][1]] = raw[i][2];

    cout << "=== Dijkstra (from 0) ===\n";
    dijkstra(g, n, 0);
    cout << "\n=== Floyd ===\n";
    floyd(g, n);
    return 0;
}

Java

import java.util.*;

public class ShortestPath {
    static final int INF = 1_000_000_000;

    // Dijkstra：单源最短路径（贪心，邻接矩阵，O(n^2)，不能有负权）
    static void dijkstra(int[][] g, int n, int src) {
        int[] dist = new int[n];
        int[] parent = new int[n];
        boolean[] visited = new boolean[n];
        Arrays.fill(dist, INF);
        Arrays.fill(parent, -1);
        dist[src] = 0;
        for (int k = 0; k < n; k++) {
            // 选未访问且距离最小的顶点
            int u = -1;
            for (int i = 0; i < n; i++)
                if (!visited[i] && (u == -1 || dist[i] < dist[u])) u = i;
            if (u == -1 || dist[u] >= INF) break;   // 剩余顶点不可达
            visited[u] = true;
            // 松弛：用 u 更新邻点距离
            for (int v = 0; v < n; v++)
                if (!visited[v] && g[u][v] < INF && dist[u] + g[u][v] < dist[v]) {
                    dist[v] = dist[u] + g[u][v];
                    parent[v] = u;
                }
        }
        // 输出距离与路径
        for (int i = 0; i < n; i++) {
            if (i == src) continue;
            if (dist[i] >= INF) { System.out.println(src + " -> " + i + ": 不可达"); continue; }
            List<Integer> path = new ArrayList<>();
            for (int cur = i; cur != -1; cur = parent[cur]) path.add(cur);
            Collections.reverse(path);
            System.out.print(src + " -> " + i + ": 距离=" + dist[i] + " 路径=");
            for (int j = 0; j < path.size(); j++) {
                if (j > 0) System.out.print(" -> ");
                System.out.print(path.get(j));
            }
            System.out.println();
        }
    }

    // Floyd：多源最短路径（动态规划，O(n^3)）
    static void floyd(int[][] g, int n) {
        int[][] d = new int[n][n];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                d[i][j] = g[i][j];

        for (int k = 0; k < n; k++)          // 枚举中间点
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    if (d[i][k] + d[k][j] < d[i][j])
                        d[i][j] = d[i][k] + d[k][j];

        System.out.println("Floyd 任意两点最短距离矩阵:");
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (d[i][j] >= INF) System.out.printf("%5s", "INF");
                else System.out.printf("%5d", d[i][j]);
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        int n = 5;
        int[][] g = new int[n][n];
        for (int[] row : g) Arrays.fill(row, INF);
        for (int i = 0; i < n; i++) g[i][i] = 0;

        // 有向带权图的边 (u, v, w)
        int[][] raw = {{0,1,10},{0,3,5},{1,2,1},{1,3,2},{3,1,3},
                       {3,2,9},{3,4,2},{2,4,4},{4,2,6}};
        for (int[] e : raw) g[e[0]][e[1]] = e[2];

        System.out.println("=== Dijkstra (from 0) ===");
        dijkstra(g, n, 0);
        System.out.println();
        System.out.println("=== Floyd ===");
        floyd(g, n);
    }
}

Python

INF = float("inf")


def dijkstra(g, n, src=0):
    """Dijkstra：单源最短路径，贪心，邻接矩阵 O(n^2)，不能有负权"""
    dist = [INF] * n
    parent = [-1] * n
    visited = [False] * n
    dist[src] = 0
    for _ in range(n):
        # 选未访问且距离最小的顶点
        u = min((v for v in range(n) if not visited[v]), key=lambda v: dist[v])
        if dist[u] == INF:          # 剩余顶点不可达
            break
        visited[u] = True
        # 松弛：用 u 更新邻点距离
        for v in range(n):
            if (not visited[v] and g[u][v] < INF
                    and dist[u] + g[u][v] < dist[v]):
                dist[v] = dist[u] + g[u][v]
                parent[v] = u

    for i in range(n):
        if i == src:
            continue
        if dist[i] == INF:
            print(f"{src} -> {i}: 不可达")
            continue
        path = []
        cur = i
        while cur != -1:
            path.append(cur)
            cur = parent[cur]
        path.reverse()
        print(f"{src} -> {i}: 距离={dist[i]} 路径=" + " -> ".join(map(str, path)))


def floyd(g, n):
    """Floyd：多源最短路径，动态规划 O(n^3)"""
    d = [row[:] for row in g]
    for k in range(n):              # 枚举中间点
        for i in range(n):
            for j in range(n):
                if d[i][k] < INF and d[k][j] < INF and d[i][k] + d[k][j] < d[i][j]:
                    d[i][j] = d[i][k] + d[k][j]

    print("Floyd 任意两点最短距离矩阵:")
    for i in range(n):
        row = []
        for j in range(n):
            row.append("INF" if d[i][j] >= INF else str(d[i][j]))
        print(" ".join(f"{x:>5}" for x in row))


if __name__ == "__main__":
    n = 5
    g = [[INF] * n for _ in range(n)]
    for i in range(n):
        g[i][i] = 0

    # 有向带权图的边 (u, v, w)
    raw = [(0,1,10),(0,3,5),(1,2,1),(1,3,2),(3,1,3),
           (3,2,9),(3,4,2),(2,4,4),(4,2,6)]
    for u, v, w in raw:
        g[u][v] = w

    print("=== Dijkstra (from 0) ===")
    dijkstra(g, n, 0)
    print()
    print("=== Floyd ===")
    floyd(g, n)