最短路

定義

（還記得這些定義嗎？在閲讀下列內容之前，請務必瞭解圖論相關概念中的基礎部分。）

路徑
最短路
有向圖中的最短路、無向圖中的最短路
單源最短路、每對結點之間的最短路

性質

對於邊權為正的圖，任意兩個結點之間的最短路，不會經過重複的結點。

對於邊權為正的圖，任意兩個結點之間的最短路，不會經過重複的邊。

對於邊權為正的圖，任意兩個結點之間的最短路，任意一條的結點數不會超過 \(n\)，邊數不會超過 \(n-1\)。

記號

為了方便敍述，這裏先給出下文將會用到的一些記號的含義。

\(n\) 為圖上點的數目，\(m\) 為圖上邊的數目；
\(s\) 為最短路的源點；
\(D(u)\) 為 \(s\) 點到 \(u\) 點的實際最短路長度；
\(dis(u)\) 為 \(s\) 點到 \(u\) 點的估計最短路長度。任何時候都有 \(dis(u) \geq D(u)\)。特別地，當最短路算法終止時，應有 \(dis(u)=D(u)\)。
\(w(u,v)\) 為 \((u,v)\) 這一條邊的邊權。

Floyd 算法

是用來求任意兩個結點之間的最短路的。

複雜度比較高，但是常數小，容易實現（只有三個 for）。

適用於任何圖，不管有向無向，邊權正負，但是最短路必須存在。（不能有個負環）

實現

我們定義一個數組 f[k][x][y]，表示只允許經過結點 \(1\) 到 \(k\)（也就是説，在子圖 \(V'={1, 2, \ldots, k}\) 中的路徑，注意，\(x\) 與 \(y\) 不一定在這個子圖中），結點 \(x\) 到結點 \(y\) 的最短路長度。

很顯然，f[n][x][y] 就是結點 \(x\) 到結點 \(y\) 的最短路長度（因為 \(V'={1, 2, \ldots, n}\) 即為 \(V\) 本身，其表示的最短路徑就是所求路徑）。

接下來考慮如何求出 f 數組的值。

f[0][x][y]：\(x\) 與 \(y\) 的邊權，或者 \(0\)，或者 \(+\infty\)（f[0][x][y] 什麼時候應該是 \(+\infty\)？當 \(x\) 與 \(y\) 間有直接相連的邊的時候，為它們的邊權；當 \(x = y\) 的時候為零，因為到本身的距離為零；當 \(x\) 與 \(y\) 沒有直接相連的邊的時候，為 \(+\infty\)）。

f[k][x][y] = min(f[k-1][x][y], f[k-1][x][k]+f[k-1][k][y])（f[k-1][x][y]，為不經過 \(k\) 點的最短路徑，而 f[k-1][x][k]+f[k-1][k][y]，為經過了 \(k\) 點的最短路）。

上面兩行都顯然是對的，所以説這個做法空間是 \(O(N^3)\)，我們需要依次增加問題規模（\(k\) 從 \(1\) 到 \(n\)），判斷任意兩點在當前問題規模下的最短路。

C++Python

for (k = 1; k <= n; k++) {
  for (x = 1; x <= n; x++) {
    for (y = 1; y <= n; y++) {
      f[k][x][y] = min(f[k - 1][x][y], f[k - 1][x][k] + f[k - 1][k][y]);
    }
  }
}

for k in range(1, n + 1):
    for x in range(1, n + 1):
        for y in range(1, n + 1):
            f[k][x][y] = min(f[k - 1][x][y], f[k - 1][x][k] + f[k - 1][k][y])

因為第一維對結果無影響，我們可以發現數組的第一維是可以省略的，於是可以直接改成 f[x][y] = min(f[x][y], f[x][k]+f[k][y])。

證明第一維對結果無影響

我們注意到如果放在一個給定第一維 k 二維數組中，f[x][k] 與 f[k][y] 在某一行和某一列。而 f[x][y] 則是該行和該列的交叉點上的元素。

現在我們需要證明將 f[k][x][y] 直接在原地更改也不會更改它的結果：我們注意到 f[k][x][y] 的涵義是第一維為 k-1 這一行和這一列的所有元素的最小值，包含了 f[k-1][x][y]，那麼在原地進行更改也不會改變最小值的值，因為如果將該三維矩陣壓縮為二維，則所求結果 f[x][y] 一開始即為原 f[k-1][x][y] 的值，最後依然會成為該行和該列的最小值。

故可以壓縮。

C++Python

for (k = 1; k <= n; k++) {
  for (x = 1; x <= n; x++) {
    for (y = 1; y <= n; y++) {
      f[x][y] = min(f[x][y], f[x][k] + f[k][y]);
    }
  }
}

for k in range(1, n + 1):
    for x in range(1, n + 1):
        for y in range(1, n + 1):
            f[x][y] = min(f[x][y], f[x][k] + f[k][y])

綜上時間複雜度是 \(O(N^3)\)，空間複雜度是 \(O(N^2)\)。

應用

給一個正權無向圖，找一個最小權值和的環。

首先這一定是一個簡單環。

想一想這個環是怎麼構成的。

考慮環上編號最大的結點 \(u\)。

f[u-1][x][y] 和 \((u,x)\),\((u,y)\) 共同構成了環。

在 Floyd 的過程中枚舉 \(u\)，計算這個和的最小值即可。

時間複雜度為 \(O(n^3)\)。

已知一個有向圖中任意兩點之間是否有連邊，要求判斷任意兩點是否連通。

該問題即是求 圖的傳遞閉包。

我們只需要按照 Floyd 的過程，逐個加入點判斷一下。

只是此時的邊的邊權變為 \(1/0\)，而取 \(\min\) 變成了或運算。

再進一步用 bitset 優化，複雜度可以到 \(O(\frac{n^3}{w})\)。

// std::bitset<SIZE> f[SIZE];
for (k = 1; k <= n; k++)
  for (i = 1; i <= n; i++)
    if (f[i][k]) f[i] = f[i] | f[k];

Bellman–Ford 算法

Bellman–Ford 算法是一種基於鬆弛（relax）操作的最短路算法，可以求出有負權的圖的最短路，並可以對最短路不存在的情況進行判斷。

在國內 OI 界，你可能聽説過的「SPFA」，就是 Bellman–Ford 算法的一種實現。

過程

先介紹 Bellman–Ford 算法要用到的鬆弛操作（Dijkstra 算法也會用到鬆弛操作）。

對於邊 \((u,v)\)，鬆弛操作對應下面的式子：\(dis(v) = \min(dis(v), dis(u) + w(u, v))\)。

這麼做的含義是顯然的：我們嘗試用 \(S \to u \to v\)（其中 \(S \to u\) 的路徑取最短路）這條路徑去更新 \(v\) 點最短路的長度，如果這條路徑更優，就進行更新。

Bellman–Ford 算法所做的，就是不斷嘗試對圖上每一條邊進行鬆弛。我們每進行一輪循環，就對圖上所有的邊都嘗試進行一次鬆弛操作，當一次循環中沒有成功的鬆弛操作時，算法停止。

每次循環是 \(O(m)\) 的，那麼最多會循環多少次呢？

在最短路存在的情況下，由於一次鬆弛操作會使最短路的邊數至少 \(+1\)，而最短路的邊數最多為 \(n-1\)，因此整個算法最多執行 \(n-1\) 輪鬆弛操作。故總時間複雜度為 \(O(nm)\)。

但還有一種情況，如果從 \(S\) 點出發，抵達一個負環時，鬆弛操作會無休止地進行下去。注意到前面的論證中已經説明了，對於最短路存在的圖，鬆弛操作最多隻會執行 \(n-1\) 輪，因此如果第 \(n\) 輪循環時仍然存在能鬆弛的邊，説明從 \(S\) 點出發，能夠抵達一個負環。

負環判斷中存在的常見誤區

需要注意的是，以 \(S\) 點為源點跑 Bellman–Ford 算法時，如果沒有給出存在負環的結果，只能説明從 \(S\) 點出發不能抵達一個負環，而不能説明圖上不存在負環。

因此如果需要判斷整個圖上是否存在負環，最嚴謹的做法是建立一個超級源點，向圖上每個節點連一條權值為 0 的邊，然後以超級源點為起點執行 Bellman–Ford 算法。

實現

參考實現

C++Python

struct Edge {
  int u, v, w;
};

vector<Edge> edge;

int dis[MAXN], u, v, w;
const int INF = 0x3f3f3f3f;

bool bellmanford(int n, int s) {
  memset(dis, 0x3f, sizeof(dis));
  dis[s] = 0;
  bool flag = false;  // 判斷一輪循環過程中是否發生鬆弛操作
  for (int i = 1; i <= n; i++) {
    flag = false;
    for (int j = 0; j < edge.size(); j++) {
      u = edge[j].u, v = edge[j].v, w = edge[j].w;
      if (dis[u] == INF) continue;
      // 無窮大與常數加減仍然為無窮大
      // 因此最短路長度為 INF 的點引出的邊不可能發生鬆弛操作
      if (dis[v] > dis[u] + w) {
        dis[v] = dis[u] + w;
        flag = true;
      }
    }
    // 沒有可以鬆弛的邊時就停止算法
    if (!flag) {
      break;
    }
  }
  // 第 n 輪循環仍然可以鬆弛時説明 s 點可以抵達一個負環
  return flag;
}

class Edge:
    def __init__(self, u = 0, v = 0, w = 0):
        self.u = u
        self.v = v
        self.w = w

INF = 0x3f3f3f3f
edge = []
dis = [INF] * MAXN

def bellmanford(n, s):
    dis[s] = 0
    for i in range(1, n + 1):
        flag = False
        for e in edge:
            u, v, w = e.u, e.v, e.w
            if dis[u] == INF:
                continue
            # 無窮大與常數加減仍然為無窮大
            # 因此最短路長度為 INF 的點引出的邊不可能發生鬆弛操作
            if dis[v] > dis[u] + w:
                dis[v] = dis[u] + w
                flag = True
        # 沒有可以鬆弛的邊時就停止算法
        if not flag:
            break
    # 第 n 輪循環仍然可以鬆弛時説明 s 點可以抵達一個負環
    return flag

隊列優化：SPFA

即 Shortest Path Faster Algorithm。

很多時候我們並不需要那麼多無用的鬆弛操作。

很顯然，只有上一次被鬆弛的結點，所連接的邊，才有可能引起下一次的鬆弛操作。

那麼我們用隊列來維護「哪些結點可能會引起鬆弛操作」，就能只訪問必要的邊了。

SPFA 也可以用於判斷 \(s\) 點是否能抵達一個負環，只需記錄最短路經過了多少條邊，當經過了至少 \(n\) 條邊時，説明 \(s\) 點可以抵達一個負環。

實現

C++Python

struct edge {
  int v, w;
};

vector<edge> e[maxn];
int dis[maxn], cnt[maxn], vis[maxn];
queue<int> q;

bool spfa(int n, int s) {
  memset(dis, 63, sizeof(dis));
  dis[s] = 0, vis[s] = 1;
  q.push(s);
  while (!q.empty()) {
    int u = q.front();
    q.pop(), vis[u] = 0;
    for (auto ed : e[u]) {
      int v = ed.v, w = ed.w;
      if (dis[v] > dis[u] + w) {
        dis[v] = dis[u] + w;
        cnt[v] = cnt[u] + 1;  // 記錄最短路經過的邊數
        if (cnt[v] >= n) return false;
        // 在不經過負環的情況下，最短路至多經過 n - 1 條邊
        // 因此如果經過了多於 n 條邊，一定説明經過了負環
        if (!vis[v]) q.push(v), vis[v] = 1;
      }
    }
  }
  return true;
}

from collections import deque
class Edge:
    def __init__(self, v = 0, w = 0):
        self.v = v
        self.w = w

e = [[Edge() for i in range(maxn)] for j in range(maxn)]
dis = [0x3f3f3f3f] * maxn; cnt = [0] * maxn; vis = [False] * maxn

q = deque()
def spfa(n, s):
    dis[s] = 0
    vis[s] = True
    q.append(s)
    while q:
        u = q.popleft()
        vis[u] = False
        for ed in e[u]:
            v, w = ed.v, ed.w
            if dis[v] > dis[u] + w:
                dis[v] = dis[u] + w
                cnt[v] = cnt[u] + 1 # 記錄最短路經過的邊數
                if cnt[v] >= n:
                    return False
                # 在不經過負環的情況下，最短路至多經過 n - 1 條邊
                # 因此如果經過了多於 n 條邊，一定説明經過了負環
                if not vis[v]:
                    q.append(v)
                    vis[v] = True

雖然在大多數情況下 SPFA 跑得很快，但其最壞情況下的時間複雜度為 \(O(nm)\)，將其卡到這個複雜度也是不難的，所以考試時要謹慎使用（在沒有負權邊時最好使用 Dijkstra 算法，在有負權邊且題目中的圖沒有特殊性質時，若 SPFA 是標算的一部分，題目不應當給出 Bellman–Ford 算法無法通過的數據範圍）。

Bellman–Ford 的其他優化

除了隊列優化（SPFA）之外，Bellman–Ford 還有其他形式的優化，這些優化在部分圖上效果明顯，但在某些特殊圖上，最壞複雜度可能達到指數級。

堆優化：將隊列換成堆，與 Dijkstra 的區別是允許一個點多次入隊。在有負權邊的圖可能被卡成指數級複雜度。
棧優化：將隊列換成棧（即將原來的 BFS 過程變成 DFS），在尋找負環時可能具有更高效率，但最壞時間複雜度仍然為指數級。
LLL 優化：將普通隊列換成雙端隊列，每次將入隊結點距離和隊內距離平均值比較，如果更大則插入至隊尾，否則插入隊首。
SLF 優化：將普通隊列換成雙端隊列，每次將入隊結點距離和隊首比較，如果更大則插入至隊尾，否則插入隊首。
D´Esopo–Pape 算法：將普通隊列換成雙端隊列，如果一個節點之前沒有入隊，則將其插入隊尾，否則插入隊首。

更多優化以及針對這些優化的 Hack 方法，可以看 fstqwq 在知乎上的回答。

Dijkstra 算法

Dijkstra（/ˈdikstrɑ/或/ˈdɛikstrɑ/）算法由荷蘭計算機科學家 E. W. Dijkstra 於 1956 年發現，1959 年公開發表。是一種求解 非負權圖 上單源最短路徑的算法。

過程

將結點分成兩個集合：已確定最短路長度的點集（記為 \(S\) 集合）的和未確定最短路長度的點集（記為 \(T\) 集合）。一開始所有的點都屬於 \(T\) 集合。

初始化 \(dis(s)=0\)，其他點的 \(dis\) 均為 \(+\infty\)。

然後重複這些操作：

從 \(T\) 集合中，選取一個最短路長度最小的結點，移到 \(S\) 集合中。
對那些剛剛被加入 \(S\) 集合的結點的所有出邊執行鬆弛操作。

直到 \(T\) 集合為空，算法結束。

時間複雜度

有多種方法來維護 1 操作中最短路長度最小的結點，不同的實現導致了 Dijkstra 算法時間複雜度上的差異。

暴力：不使用任何數據結構進行維護，每次 2 操作執行完畢後，直接在 \(T\) 集合中暴力尋找最短路長度最小的結點。2 操作總時間複雜度為 \(O(m)\)，1 操作總時間複雜度為 \(O(n^2)\)，全過程的時間複雜度為 \(O(n^2 + m) = O(n^2)\)。
二叉堆：每成功鬆弛一條邊 \((u,v)\)，就將 \(v\) 插入二叉堆中（如果 \(v\) 已經在二叉堆中，直接修改相應元素的權值即可），1 操作直接取堆頂結點即可。共計 \(O(m)\) 次二叉堆上的插入（修改）操作，\(O(n)\) 次刪除堆頂操作，而插入（修改）和刪除的時間複雜度均為 \(O(\log n)\)，時間複雜度為 \(O((n+m) \log n) = O(m \log n)\)。
優先隊列：和二叉堆類似，但使用優先隊列時，如果同一個點的最短路被更新多次，因為先前更新時插入的元素不能被刪除，也不能被修改，只能留在優先隊列中，故優先隊列內的元素個數是 \(O(m)\) 的，時間複雜度為 \(O(m \log m)\)。
Fibonacci 堆：和前面二者類似，但 Fibonacci 堆插入的時間複雜度為 \(O(1)\)，故時間複雜度為 \(O(n \log n + m)\)，時間複雜度最優。但因為 Fibonacci 堆較二叉堆不易實現，效率優勢也不夠大¹，算法競賽中較少使用。
線段樹：和二叉堆原理類似，不過將每次成功鬆弛後插入二叉堆的操作改為在線段樹上執行單點修改，而 1 操作則是線段樹上的全局查詢最小值。時間複雜度為 \(O(m \log n)\)。

在稀疏圖中，\(m = O(n)\)，使用二叉堆實現的 Dijkstra 算法較 Bellman–Ford 算法具有較大的效率優勢；而在稠密圖中，\(m = O(n^2)\)，這時候使用暴力做法較二叉堆實現更優。

正確性證明

下面用數學歸納法證明，在 所有邊權值非負 的前提下，Dijkstra 算法的正確性²。

簡單來説，我們要證明的，就是在執行 1 操作時，取出的結點 \(u\) 最短路均已經被確定，即滿足 \(D(u) = dis(u)\)。

初始時 \(S = \varnothing\)，假設成立。

接下來用反證法。

設 \(u\) 點為算法中第一個在加入 \(S\) 集合時不滿足 \(D(u) = dis(u)\) 的點。因為 \(s\) 點一定滿足 \(D(u)=dis(u)=0\)，且它一定是第一個加入 \(S\) 集合的點，因此將 \(u\) 加入 \(S\) 集合前，\(S \neq \varnothing\)，如果不存在 \(s\) 到 \(u\) 的路徑，則 \(D(u) = dis(u) = +\infty\)，與假設矛盾。

於是一定存在路徑 \(s \to x \to y \to u\)，其中 \(y\) 為 \(s \to u\) 路徑上第一個屬於 \(T\) 集合的點，而 \(x\) 為 \(y\) 的前驅結點（顯然 \(x \in S\)）。需要注意的是，可能存在 \(s = x\) 或 \(y = u\) 的情況，即 \(s \to x\) 或 \(y \to u\) 可能是空路徑。

因為在 \(u\) 結點之前加入的結點都滿足 \(D(u) = dis(u)\)，所以在 \(x\) 點加入到 \(S\) 集合時，有 \(D(x) = dis(x)\)，此時邊 \((x,y)\) 會被鬆弛，從而可以證明，將 \(u\) 加入到 \(S\) 時，一定有 \(D(y)=dis(y)\)。

下面證明 \(D(u) = dis(u)\) 成立。在路徑 \(s \to x \to y \to u\) 中，因為圖上所有邊邊權非負，因此 \(D(y) \leq D(u)\)。從而 \(dis(y) \leq D(y) \leq D(u)\leq dis(u)\)。但是因為 \(u\) 結點在 1 過程中被取出 \(T\) 集合時，\(y\) 結點還沒有被取出 \(T\) 集合，因此此時有 \(dis(u)\leq dis(y)\)，從而得到 \(dis(y) = D(y) = D(u) = dis(u)\)，這與 \(D(u)\neq dis(u)\) 的假設矛盾，故假設不成立。

因此我們證明了，1 操作每次取出的點，其最短路均已經被確定。命題得證。

注意到證明過程中的關鍵不等式 \(D(y) \leq D(u)\) 是在圖上所有邊邊權非負的情況下得出的。當圖上存在負權邊時，這一不等式不再成立，Dijkstra 算法的正確性將無法得到保證，算法可能會給出錯誤的結果。

實現

這裏同時給出 \(O(n^2)\) 的暴力做法實現和 \(O(m \log m)\) 的優先隊列做法實現。

暴力實現

C++Python

struct edge {
  int v, w;
};

vector<edge> e[maxn];
int dis[maxn], vis[maxn];

void dijkstra(int n, int s) {
  memset(dis, 63, sizeof(dis));
  dis[s] = 0;
  for (int i = 1; i <= n; i++) {
    int u = 0, mind = 0x3f3f3f3f;
    for (int j = 1; j <= n; j++)
      if (!vis[j] && dis[j] < mind) u = j, mind = dis[j];
    vis[u] = true;
    for (auto ed : e[u]) {
      int v = ed.v, w = ed.w;
      if (dis[v] > dis[u] + w) dis[v] = dis[u] + w;
    }
  }
}

class Edge:
    def __init(self, v = 0, w = 0):
        self.v = v
        self.w = w
e = [[Edge() for i in range(maxn)] for j in range(maxn)]
dis = [0x3f3f3f3f] * maxn; vis = [0] * maxn
def dijkstra(n, s):
    dis[s] = 0
    for i in range(1, n + 1):
        u = 0
        mind = 0x3f3f3f3f
        for j in range(1, n + 1):
            if not vis[j] and dis[j] < mind:
                u = j
                mind = dis[j]
        vis[u] = True
        for ed in e[u]:
            v, w = ed.v, ed.w
            if dis[v] > dis[u] + w:
                dis[v] = dis[u] + w

優先隊列實現

C++Python

struct edge {
  int v, w;
};

struct node {
  int dis, u;

  bool operator>(const node& a) const { return dis > a.dis; }
};

vector<edge> e[maxn];
int dis[maxn], vis[maxn];
priority_queue<node, vector<node>, greater<node> > q;

void dijkstra(int n, int s) {
  memset(dis, 63, sizeof(dis));
  dis[s] = 0;
  q.push({0, s});
  while (!q.empty()) {
    int u = q.top().u;
    q.pop();
    if (vis[u]) continue;
    vis[u] = 1;
    for (auto ed : e[u]) {
      int v = ed.v, w = ed.w;
      if (dis[v] > dis[u] + w) {
        dis[v] = dis[u] + w;
        q.push({dis[v], v});
      }
    }
  }
}

def dijkstra(e,s):
  '''
  輸入：
  e:鄰接表
  s:起點
  返回：
  dis:從s到每個頂點的最短路長度
  '''
  dis = defaultdict(lambda:float("inf"))
  dis[s] = 0
  q = [(0,s)]
  vis = set()
  while q:
      _, u = heapq.heappop(q)
      if u in vis: continue
      vis.add(u)
      for v,w in e[u]:
          if dis[v] > dis[u] + w:
              dis[v] = dis[u] + w
              heapq.heappush(q,(dis[v],v))
  return dis

Johnson 全源最短路徑算法

Johnson 和 Floyd 一樣，是一種能求出無負環圖上任意兩點間最短路徑的算法。該算法在 1977 年由 Donald B. Johnson 提出。

任意兩點間的最短路可以通過枚舉起點，跑 \(n\) 次 Bellman–Ford 算法解決，時間複雜度是 \(O(n^2m)\) 的，也可以直接用 Floyd 算法解決，時間複雜度為 \(O(n^3)\)。

注意到堆優化的 Dijkstra 算法求單源最短路徑的時間複雜度比 Bellman–Ford 更優，如果枚舉起點，跑 \(n\) 次 Dijkstra 算法，就可以在 \(O(nm\log m)\)（取決於 Dijkstra 算法的實現）的時間複雜度內解決本問題，比上述跑 \(n\) 次 Bellman–Ford 算法的時間複雜度更優秀，在稀疏圖上也比 Floyd 算法的時間複雜度更加優秀。

但 Dijkstra 算法不能正確求解帶負權邊的最短路，因此我們需要對原圖上的邊進行預處理，確保所有邊的邊權均非負。

一種容易想到的方法是給所有邊的邊權同時加上一個正數 \(x\)，從而讓所有邊的邊權均非負。如果新圖上起點到終點的最短路經過了 \(k\) 條邊，則將最短路減去 \(kx\) 即可得到實際最短路。

但這樣的方法是錯誤的。考慮下圖：

\(1 \to 2\) 的最短路為 \(1 \to 5 \to 3 \to 2\)，長度為 \(−2\)。

但假如我們把每條邊的邊權加上 \(5\) 呢？

新圖上 \(1 \to 2\) 的最短路為 \(1 \to 4 \to 2\)，已經不是實際的最短路了。

Johnson 算法則通過另外一種方法來給每條邊重新標註邊權。

我們新建一個虛擬節點（在這裏我們就設它的編號為 \(0\)）。從這個點向其他所有點連一條邊權為 \(0\) 的邊。

接下來用 Bellman–Ford 算法求出從 \(0\) 號點到其他所有點的最短路，記為 \(h_i\)。

假如存在一條從 \(u\) 點到 \(v\) 點，邊權為 \(w\) 的邊，則我們將該邊的邊權重新設置為 \(w+h_u-h_v\)。

接下來以每個點為起點，跑 \(n\) 輪 Dijkstra 算法即可求出任意兩點間的最短路了。

一開始的 Bellman–Ford 算法並不是時間上的瓶頸，若使用 priority_queue 實現 Dijkstra 算法，該算法的時間複雜度是 \(O(nm\log m)\)。

正確性證明

為什麼這樣重新標註邊權的方式是正確的呢？

在討論這個問題之前，我們先討論一個物理概念——勢能。

諸如重力勢能，電勢能這樣的勢能都有一個特點，勢能的變化量只和起點和終點的相對位置有關，而與起點到終點所走的路徑無關。

勢能還有一個特點，勢能的絕對值往往取決於設置的零勢能點，但無論將零勢能點設置在哪裏，兩點間勢能的差值是一定的。

接下來回到正題。

在重新標記後的圖上，從 \(s\) 點到 \(t\) 點的一條路徑 \(s \to p_1 \to p_2 \to \dots \to p_k \to t\) 的長度表達式如下：

\((w(s,p_1)+h_s-h_{p_1})+(w(p_1,p_2)+h_{p_1}-h_{p_2})+ \dots +(w(p_k,t)+h_{p_k}-h_t)\)

化簡後得到：

\(w(s,p_1)+w(p_1,p_2)+ \dots +w(p_k,t)+h_s-h_t\)

無論我們從 \(s\) 到 \(t\) 走的是哪一條路徑，\(h_s-h_t\) 的值是不變的，這正與勢能的性質相吻合！

為了方便，下面我們就把 \(h_i\) 稱為 \(i\) 點的勢能。

上面的新圖中 \(s \to t\) 的最短路的長度表達式由兩部分組成，前面的邊權和為原圖中 \(s \to t\) 的最短路，後面則是兩點間的勢能差。因為兩點間勢能的差為定值，因此原圖上 \(s \to t\) 的最短路與新圖上 \(s \to t\) 的最短路相對應。

到這裏我們的正確性證明已經解決了一半——我們證明了重新標註邊權後圖上的最短路徑仍然是原來的最短路徑。接下來我們需要證明新圖中所有邊的邊權非負，因為在非負權圖上，Dijkstra 算法能夠保證得出正確的結果。

根據三角形不等式，圖上任意一邊 \((u,v)\) 上兩點滿足：\(h_v \leq h_u + w(u,v)\)。這條邊重新標記後的邊權為 \(w'(u,v)=w(u,v)+h_u-h_v \geq 0\)。這樣我們證明了新圖上的邊權均非負。

這樣，我們就證明了 Johnson 算法的正確性。

不同方法的比較

最短路算法	Floyd	Bellman–Ford	Dijkstra	Johnson
最短路類型	每對結點之間的最短路	單源最短路	單源最短路	每對結點之間的最短路
作用於	任意圖	任意圖	非負權圖	任意圖
能否檢測負環？	能	能	不能	能
時間複雜度	\(O(N^3)\)	\(O(NM)\)	\(O(M\log M)\)	\(O(NM\log M)\)

注：表中的 Dijkstra 算法在計算複雜度時均用 priority_queue 實現。

輸出方案

開一個 pre 數組，在更新距離的時候記錄下來後面的點是如何轉移過去的，算法結束前再遞歸地輸出路徑即可。

比如 Floyd 就要記錄 pre[i][j] = k;，Bellman–Ford 和 Dijkstra 一般記錄 pre[v] = u。

參考資料與註釋

Worst case of fibonacci heap - Wikipedia ↩
《算法導論（第 3 版中譯本）》，機械工業出版社，2013 年，第 384 - 385 頁。 ↩

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：du33169
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用