# 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

```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++

```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

```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

```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)
```