網格圖負權最短路

02-25

單身狗們大家節日快樂呢。

之前想把這篇拖到新年的時候發的，現在想想也不失為一種諷刺，因此只是按照時間把舊作發出來而已。

雖然希望自己是一個冷淡的人，不過大概還是沒完全做到吧，舊的一年裡，關心過幫助過我的人，非常感謝。

通常來說我特意許下的願望都不怎麼會實現，但這個願望我相信應該會實現的——遇到能夠改變自己的人，很期待這次相遇呢。如果實現不了的話感覺我這些無謂的掙扎就沒什麼意義了呢（笑）。

喪氣的話不多說了，祝各位新年愉快。

若 $G$ 的節點數不大於 2 ，直接返回
沿著 $G$ 的長邊的中點把 $G$ 分為 $G_0,G_1$
取中線上一點 $r$
$D_i=shortest-path(G_i,r)$
算出 $G_i$ 中任意兩個中線上的點的距離 $delta_i[u][v]$
對每個邊界上的點 $v$ 算出 $B[v]=dist(r,v)$
對每個點 $v$ 算出 $d[v]=dist(r,v)$
對每個點 $v$ 算出 $d[v]=dist(s,v)$
$d$ 即為所求

Cost function

我們的演算法主要基於 cost function 構建，事實上 Dijkstra 除了無法應對負權已經是足夠優秀的演算法了，為了能夠讓其處理負權，我們把原圖中的距離 $L(u,v)$ 映射到非負的 $L_phi(u,v)=L(u,v)+phi(u)-phi(v)$ 距離上，由於顯然 $L_phi(u,v)+L_phi(v,w)=L(u,v)+L(v,w)+phi(u)-phi(w)$ ，因此轉換後的距離也是可以直接用 Dijkstra 求解的。

$L_phi(u,v)$ 非負需要選取合適的代價函數 $phi(v)$ 。

以 Step 8 為例，由於 $dist(u,v)+dist(r,u)-dist(r,v)geqslant 0$ ，因此令 $phi(v)=d[v]$ 即可。

Step 6

for v in V: e[0][v] = infe[0][r] = 0for i in range(1, len(V) + 1): for v in V: e[i][v] = inf for w in V: e[i][v] = min(e[i][v], e[i - 1][w] + delta[i % 2][w][v])for v in V: B[v] = e[len(V)][v]

先來看一段暴力，這段比較顯然的暴力可以在 $O(|V|^3)$ 的時間內求出結果。

考慮每一步轉移，我們實際上是在找 $delta_{imod 2}[w][v]+e[i - 1][w]$ 的列最小值。

如果一個 $n imes n$ 的矩陣滿足 Monge Property ( $A_{i,k}+A_{j,l}leqslant A_{i,l}+A_{j,k}forall i<j,k<l$ ) 則我們可以在 $O(|V|)$ 的時間裡求出每一列的最小值。

注意到 Monge Property 保證了每列的最小值位置是單調不降的。

$O(|V|log |V|)$ : 暴力按決策單調性處理

$O(|V|)$ : 注意到我們如果知道奇數列的最小值以後，偶數列的最小值是可以用一次掃描求出的，因此可以遞歸對所有奇數列求解，用以下的演算法可以把 $n imes m$ 的矩陣縮成 $m imes m$ 的：

reduce(A): Q = A k = 1 while row(Q) > m: if Q[k][k] < Q[k + 1][k]: if k < n: k += 1 else: Q.deleteRow(m + 1) else: Q.deleteRow(k) if k > 1: k -= 1 return Q

根據單調性的性質代碼的正確性應該比較顯然。

然而矩陣不一定滿足 Monge Property ，當 $i<k<j<l$ 的時候無法這麼分析。

每次把矩陣切成 4 份，注意到右上和左下都滿足 Monge Property ，對另兩個遞歸。

總複雜度 $O(nlog n)$ 。

Step 5

我們假定此處處理時滿足邊權非負，代價函數 $phi(v)=D_i(v)$ 。

我們順著中線掃描，維護以每個點為根的最短路樹，可以觀察到每條邊會在連續一段區間的最短路樹上出現。

維護最短路樹和對偶圖上的樹。每一條對偶圖樹的邊對應了一條非樹邊，權值為 $t(uv)=d(r,v)-d(r,u)-L_phi(u,v)$ ， $t(uv)>0$ 表示需要鬆弛。

計算 $v_{i+1}$ 的最短路樹的時候，首先把根從 $v_i$ 移動過來，刪除 $v_{i+1}$ 的入邊，連上 $v_{i+1}v_i$ 。

然後進行鬆弛，令 $P(e)$ 為對偶圖樹中 $e^*$ 對應的路徑，在對偶圖樹上查詢 $P(v_iv_{i+1})$ 上的 $t(uv)$ 最大的邊，如果 $t(uv)>0$ 就進行鬆弛（並對兩棵樹進行操作，刪去 $v$ 的入邊，加上 $uv$ ），鬆弛操作後給 $P(e)$ 上減去 $t(uv)$ （ $e$ 為 $v$ 刪掉的入邊）。

由於每條邊只會被操作常數次因此複雜度是 $O(|V|log |V|)$ ，單次詢問是 $O(log n)$ 的。

在此基礎上計算中線上任意兩點的距離，複雜度 $O(nlog n)$ 。