最短路径

一、Dijkstra 算法（单源最短路径）

适用场景

• 求一个源点到其他所有顶点的最短路径
• 不能有负权边

算法思想

贪心策略，每次选择距离源点最近的未访问顶点，用它更新其他顶点的距离。

void Dijkstra(MGraph G, int v0) {
    int dist[MaxVertexNum], path[MaxVertexNum];
    bool visited[MaxVertexNum];
    for (int i = 0; i < G.vexnum; i++) {
        dist[i] = G.edge[v0][i];
        path[i] = (dist[i] < INF) ? v0 : -1;
        visited[i] = false;
    }
    dist[v0] = 0; visited[v0] = true;
    for (int i = 1; i < G.vexnum; i++) {
        int min = INF, u = -1;
        for (int j = 0; j < G.vexnum; j++)
            if (!visited[j] && dist[j] < min) { min = dist[j]; u = j; }
        visited[u] = true;
        for (int w = 0; w < G.vexnum; w++)
            if (!visited[w] && dist[u] + G.edge[u][w] < dist[w]) {
                dist[w] = dist[u] + G.edge[u][w];
                path[w] = u;
            }
    }
}

时间复杂度 $O(|V|^2)$。

二、Floyd 算法（多源最短路径）

适用场景

• 求任意两点之间的最短路径
• 不能有负权回路

状态转移方程

$$A^{(k)}[i][j] = \min\big(A^{(k-1)}[i][j],\; A^{(k-1)}[i][k] + A^{(k-1)}[k][j]\big)$$

void Floyd(MGraph G) {
    int A[MaxVertexNum][MaxVertexNum];
    for (int i = 0; i < G.vexnum; i++)
        for (int j = 0; j < G.vexnum; j++)
            A[i][j] = G.edge[i][j];
    for (int k = 0; k < G.vexnum; k++)          // k 必须在最外层
        for (int i = 0; i < G.vexnum; i++)
            for (int j = 0; j < G.vexnum; j++)
                if (A[i][k] + A[k][j] < A[i][j])
                    A[i][j] = A[i][k] + A[k][j];
}

时间复杂度 $O(|V|^3)$。

三、Dijkstra vs Floyd

四、最短路径性质

1. 最优子结构：最短路径的子路径也是最短路径
2. Dijkstra 不能处理负权边：贪心策略失效
3. Floyd 不能有负权回路：路径长度无下界

例 1：Dijkstra（从 A）

最短路径：A→D:1，A→C:5，A→E:7（A→D→E），A→B:8（A→C→B）。

例 2：Floyd（3 顶点）

    0   1   2
0 [ 0   4  11 ]
1 [ 6   0   2 ]
2 [ 3  999  0 ]

依次允许经过中间顶点 0、1、2，最终：

    0   1   2
0 [ 0   4   6 ]
1 [ 5   0   2 ]
2 [ 3   7   0 ]

例如 $A[1][0]=5$ 对应路径 $1→2→0$（$2+3=5$）。