大概是論文的翻譯，我懶得實現了（咕咕咕，咕）萬一有人實現出來比 \(\text{dijkstra}\) 快呢。

原文網址：A Randomized Algorithm for Single-Source Shortest Path on Undirected Real-Weighted Graphs

大意就是非負實數邊權的期望復雜度比原版 \(\text{Dijsktra}\) 低的無向圖單源最短路，只使用比較和 \(+\)，默認你會 斐波那契堆。

符號約定

\(G=(V,E)\) 表示圖，\(V\) 表示點集，\(E\) 表示邊集，不失一般性，\(G\) 是連通圖。

我們認為圖是比較稀疏的，也就是 \(m=o(n\log n)\)，否則這個算法和 \(\text{dijkstra}\) 就沒有什么區別了。

\(s\) 表示起點，\(d(x,y)\) 表示 \(x\) 到 \(y\) 的最短距離，特別地 \(d(t)=d(s,t)\)。因為是無向圖，總有 \(d(x,y)=d(y,x)\)。

\(w(x,y)=w_{x,y}\) 表示 \(x\) 與 \(y\) 之間的邊權。

用 \(w\) 松弛 \(d(x,y)\) 表示 \(d(x,y)\leftarrow\min(d(x,y),w)\)。

用 \(x\rightarrow y\rightharpoonup z\rightarrow w\) 表示一條 \(x\) 到 \(w\) 的路徑，中途經過 \(y,z\)，并且路徑上 \(y\) 的下一個點是 \(z\)。

為什么可以這么快

你不要騙我，基于比較的最短路算法有下界 \(O(m+n\log n)\)。

復雜度下界的結論來自 A Shortest Path Algorithm for Real-Weighted Undirected Graphs | SIAM Journal on Computing。原文的結論更強一點，給出的下界是 \(O(m+n\min\{\log\log r,\log n\})\)，這里 \(r\) 是和值域相關的，我們這里考慮實數邊權所以不用管。

但是原文的做法大概是說存在一種點的排列，使得你的復雜度一定可以達到這個下界，但是這里是隨機化做法，所以期望復雜度可以更低。

準備工作：圖的三度化

考慮一個點的鄰居集合 \(N(u)=\{v:(u,v)\in E\}\)，我們把點 \(u\) 變成一個環，環上的邊權都是 \(0\)，環上每個點都連接一個原本的 \(v\)，容易發現這樣不影響 \(d\)。

如此，我們就得到一個有 \(O(m)\) 條邊和 \(O(m)\) 個點的圖，并且每個點的度數都不超過 \(3\)。

隨機最短路

分塊

奇怪的翻譯

分塊最短路

\(\text{Dijkstra}\) 是一個很好的算法，我們可以考慮隨機撒點跑 \(\text{Dijkstra}\)，然后再維護散點到這些點的距離，最后計算出所有的 \(d\)。

形式化地，我們以一個概率 \(p\) 把點加入 \(R\)，只有 \(R\) 中的點會被加入堆中。

圖分塊與球

對于散點，一個很 \(\text{naive}\) 的想法就是把其歸到距離最近的 \(u\in R\) 所屬的“塊”中（原文是 \(\text{bundle}\)，我不知道怎么翻譯比較好）。

其實這個 \(\text{trick}\) 還是挺常見的，對于一個點 \(v\)，我們把 \(R\) 中距其最近的點記為 \(b(v)\)，形式化地，\(\forall r\in R,d(v,r)\geqslant d\big(v,b(v)\big)\)。同時，我們額外定義球：\(\text{Ball}(v)=\{u:d(v,u)<d\big(v,b(v)\big)\}\)。（這里和原文有點不一樣，原文中 \(v\not\in\text{Ball}(v)\)，這里 \(v\in\text{Ball}(v)\)）

然后定義一個點所在的塊為 \(\text{Bundle}(u)=\{v:b(v)=u\}\)。我們認為 \(b(u)=u,\forall u\in R\)，顯然，所有 \(\text{Bundle}\) 構成了 \(V\) 的一個劃分。

球的求解

注意到在 \(\text{Dijkstra}\) 算法中，每次從堆頂取出的點已經求得了最短路，于是 \(\forall v\not\in R\)，都跑一遍 \(\text{Dijkstra}\)，當堆頂取出的點在 \(R\) 中時就停止，這個點就是 \(b(v)\)。

我們記對于 \(v\) 求解 \(\text{Ball}(v)\) 時堆中壓入的元素集合為 \(S_v\)，那么顯然 \(\text{Ball}(v)\subset S_v\)，因為 \(b(v)\) 和堆中余下的元素不屬于 \(\text{Ball}(v)\)。因為 \(R\) 是逐點隨機選的，于是 \(\mathbb{E}(R)=mp,\mathbb{E}(|S_v|)=\frac1p\)。

因為我們已經把 \(G\) 三度化了，所以每次只會加入 \(O(1)\) 個點。于是堆中的元素個數也是 \(O(|S_v|)\)。

于是求解球的復雜度就是

算法思路

整點的最短路

整體的思路就是隨機撒點跑普通 \(\text{Dijkstra}\)，然后跑了一個點 \(x\)，就要把其對應的塊 \(\text{Bundle}(x)\) 中的點的最短路都處理好。

首先，我們考慮 \(r\in R\) 的點。

假設有一條路徑 \(p:s\rightarrow x\rightarrow r\)，那么 \(|p|\ge d(s,x)+d(x,r)\)。

根據 \(\text{Bundle}\) 的定義，\(d(x,r)\ge d(x,b(x))\)，于是 \(|p|\ge d(s,x)+d(x,b(x))\)。因為 \(s\rightarrow b(x)\) 的最短路不一定經過 \(x\)，所以 \(|p|\ge d(s,x)+d(x,b(x))\ge d(s,b(x))\)。

然后我們取 \(p\) 是 \(s\rightarrow r\) 的最短路，那么 \(|p|=d(s,r)\ge d(s,b(x)),\forall x\in p\)，也就是對于路徑上的點 \(x\)，都有 \(d(b(x))\le d(r)\)。

又發現 \(\forall x,b(x)\in R\)，根據每個塊都會被處理好的假設，到 \(r\in R\) 的最短路上的點都會被處理好。

上面證明了，只要散點的最短路求出，整點 \(r\) 的最短路只能由已經處理好的點貢獻。

非常 \(\text{naive}\) 的想法就是枚舉所有可能的邊，這樣的邊只能來自 \(\text{Bundle}(r)\) 和 \(x\in\text{Bundle}(r),N(x)\)。

對于 \(x\in \text{Bundle}(r)\)，用 \(d(x)+d(x,r)\) 松弛 \(r\) 即可。

對于 \(x\in \text{Bundle}(r),y\in N(x)\)，枚舉 \(z\in N(y)\)，如果 \(z\in\text{Bundle}(r)\)，就用 \(d(y)+w(y,z)+d(z,r)\) 松弛 \(r\)。（注意到 \(y\) 只會有 \(O(1)\) 個鄰居）

散點的處理

對于 \(v\not\in R\)，如果 \(s\rightarrow v\) 的最短路上的點 \(x\) 都滿足 \(d(b(x))\le d(b(v))\)，那么和上面進行一樣的處理就可以了。

假設最短路 \(p\) 上有至少一個點 \(y\) 滿足 \(b(y)\ne b(v),d(b(y))\ge d(b(v))\)。取等是因為相同距離的 \(r\in R\) 彈出堆頂的時間也是不一樣的，但如果 \(r_1,r_2\in R\)，這個差異不會影響答案，除非 \(d(r_1,r_2)=0\)，但這樣的話 \(r_1,r_2\) 可以縮成一個點。

同時，這樣的最短路 \(p\) 至少要滿足 \(|p|=d(s,v)< d(s,b(v))+d(b(v),v)\)。因為 \(b(v)\in R\)，走到 \(b(v)\) 是可以不經過 \(y\) 的，\(b(v)\rightarrow v\) 的最短路也在 \(\text{Ball}(v)\) 內。如果 \(\ge\) 的話則和假設矛盾。

根據最短路的假設，我們知道 \(d(s,v)=d(s,y)+d(y,v)\)，也就是 \(d(y,v)=d(s,v)-d(s,y)\)。

根據假設，有 \(d(s,v)<d(s,b(v))+d(b(v),v)\) 和 \(d(b(y))<d(b(v))\)；根據三角不等式，又有 \(d(s,y)+d(y,b(y))\le d(s,b(y))\)。

可得

假設 \(z_1\) 是 \(p:s\rightarrow y\rightarrow v\) 上最后一個滿足 \(d(y,z_1)\le d(y,b(y))\) 的點。根據 \(\text{Ball}\) 的定義，\(z_1\in\text{Ball}(y)\)。

如果 \(z_1=v\)，那么我們只需要用 \(N(v)\) 中的點松弛 \(v\) 就可以了。

否則，\(p\) 可表示為 \(s\rightarrow z_1\rightharpoonup z_2\rightarrow v\)，那么根據假設有 \(d(y,z_2)>d(y,b(y))\)。

因為 \(p\) 是最短路，所以有 \(d(y,v)=d(y,z_2)+d(z_2,v)\le d(b(v),v)+d(y,b(y))\)，立刻得到 \(d(z_2,v)<d(b(v),v)\)。

于是根據 \(\text{Ball}\) 的定義，我們知道 \(z_2\in\text{Ball}(v)\)。這樣的話我們維護 \(d(v)\) 時枚舉 \(z_1,z_2\) 即可。

Bundle Dijkstra

算法流程

總結一下上面的思路，我們稍微簡化一下，可能還處理了一下正確性的細節，可以得到算法流程（已經三度化并求解 \(\text{Bundle}\) 和 \(\text{Ball}\)）：

首先，置 \(d(s)=0,\forall x\ne s,d(x)=+\infty\)，把 \(R\) 中的節點加入斐波那契堆（如果是 \(m=O(n)\) 的稀疏圖，用別的堆也沒有關系）。

然后，每次取出堆頂 \(u\)：

1. \(\forall v\in\text{Bundle}(u)\)，用 \(d(s,u)+d(u,v)\) 松弛 \(v\)（\(d(u,v)\) 在分塊時已經求出），然后 \(\forall z_2\in\text{Ball}(v)\)，用 \(d(s,y)+d(y,v)\) 松弛 \(v\)，再 \(\forall z\in N(y)\)，用 \(d(s,z)+w(z,y)+d(y,v)\) 松弛 \(v\)。
2. 在上面的步驟完成后，\(\forall v\in\text{Bundle}(u),\forall y\in N(v),\forall z\in\text{Ball}(y)\)，用 \(d(s,v)+w(v,y)\) 松弛 \(y\)，用 \(d(s,v)+w(v,y)+d(y,z)\) 松弛 \(z\)。
3. 第二步中，松弛任意點 \(x\) 的同時用 \(d(s,x)+d(x,b(x))\) 松弛 \(b(x)\)。

正確性證明

要維護的性質

不妨設從 \(R\) 中取出的第 \(i\) 個點為 \(u_i\)，\(u_0=s\)，我們只需要證明下面 \(3\) 條性質：

1. 當 \(u\) 從堆頂被取出時，\(d(u)\) 已經是正確的
2. 同普通 \(\text{Dijkstra}\) 一樣，滿足 \(d(u_i)\ge d(u_j)\) 當 \(i\ge j\) 時。（注意這里是臨時維護的答案，不是真的最短距離）
3. 進行 \(\text{Bundle Dijkstra}\) 后，\(\text{Bundle}(u_i)\) 中的點都確實是最短路

考慮數學歸納法。

初始情況

首先，\(u_0=s\)，\(\text{Bundle}(u_0)\) 中的點在求解 \(\text{Bundle}\) 時就已經處理好了，性質 \(1,3\) 顯然正確。

然后此時只有 \(d(s)=0\)，\(\forall u_k\ne s,d(u_k)=+\infty\)，于是性質 \(2\) 也成立。

性質 1

假設 \(u_0\ldots u_{k-1}\) 都處理好了，下面證明對于 \(u_k\)，性質 \(1\) 成立。

設 \(\text{B}_i=\bigcup_{j=0}^i\text{Bundle}(u_j)\)，那么 \(B_{k-1}\) 就是已經處理好的點的集合，如果 \(s\rightarrow u_k\) 的最短路只經過了 \(B_{k-1}\) 中的點，那么顯然是對的。（因為就和普通 \(\text{Dijkstra}\) 沒有區別了）

設 \(p:s\rightarrow x\rightharpoonup y\rightarrow u_k\)，其中 \(x\) 是 \(p\) 上最后一個滿足 \(x\in B_{k-1}\) 的點。

注意到 \(d(y,b(y))\le d(y,u_k)\)（如果 \(b(y)=u_k\)，成立；否則，根據 \(\text{Ball}\) 的定義，成立），于是

根據假設，可以知道 \(b(y)=u_l,l\ge k\)，根據假設有 \(d(b(y))\ge d(u_k)\)。

于是上面不等式鏈中的不等號全部應該是等于，那么 \(d(b(y))=d(u_k)=d(y)+d(y,b(y))\) 并且 \(d(y,b(y))=d(y,u_k)\)。根據算法步驟 \(2\)，\(b(y)\) 會作為 \(z\) 被枚舉到。所以，如果此時 \(d(u_k)\) 不正確，那么先彈出的就應該是 \(b(y)\)，矛盾。故 \(d(u_k)\) 的值已經是正確的了。

性質 2

假設計算完 \(\text{Bundle}(u_k)\) 后，就出現了一個點 \(u_l\in R\) 滿足 \(l>k>j\land d(u_l)<d(u_j)\)。那么這時計算的路徑一定是 \(s\rightarrow x\rightarrow u_l\)，其中 \(x\in\text{Bundle}(u_k)\)。

仿照 整點的處理 一節中的做法，根據 \(\text{Ball}\) 的定義 \(d(x,u_l)\ge d(x,u_k)\)，而我們至多是用 \(d(x)+d(x,u_l)\) 來松弛 \(u_l\)，那么必有 \(d(u_l)\ge d(x)+d(x, u_k)\ge d(u_k)\ge d(u_j)\)，與假設矛盾。于是性質 \(2\) 總是成立。

性質 3

假設有一個點 \(v\in\text{Bundle}(u_i)\)，在計算完 \(u_i\) 之后，我們維護的 \(d^\prime(v)>d(v)\)。

設 \(s\) 到 \(v\) 真正的最短路為 \(p:s\rightarrow x\rightharpoonup y\rightarrow v\)，其中 \(x\) 是 \(p\) 上最后一個滿足 \(x\in B_{i-1}\) 的點，那么就有 \(d(y,b(y))\ge d(y,u_i)\)。參考 散點的處理 一節，此時 \(p\) 也可寫成 \(s\rightarrow x\rightharpoonup y\rightarrow z_1\rightharpoonup z_2\rightarrow v\) 的形式，\(z_1,z_2\) 的含義和之前相同。（這里其實省略一些特殊情況，因為 \(z_1,z_2\) 有可能就是 \(x,y\)）

在計算 \(\text{Bundle}(u_i)\) 之前，\(d(x)\) 就已經被正確地維護了，然后算法的步驟二中的 \(z\) 會找到這條最短路上的 \(z_1\)，并給出正確的 \(d(z_1)\)，否則 \(p\) 不會是最短路。

同時，\(d(z_2,v)\) 在求解 \(\text{Ball}\) 的過程中就被求出了，于是 \(d(s,z_1)+w(z_1,z_2)+d(z_2,v)\) 會給出正確的 \(d(v)\)，矛盾。性質 \(3\) 同樣總是成立。

時間復雜度

易得，堆的復雜度為 \(O(|R|\log n)=O(mp\log n)\)。

然后預處理的復雜度為 \(O(\frac mp\log\frac 1p)\)。

\(\text{Bundle Dijkstra}\) 中看上去枚舉了很多點，但是因為 \(\forall v\in V,|N(v)|\le 3\)，于是每個 \(\text{Ball}(v)\) 只會被枚舉 \(O(1)\) 次，總的復雜度就是 \(O(\sum_{v\not\in R}|\text{Ball}(v)|)=O(\frac mp)\)。

求導易知 \(p=\sqrt{\frac{\log\log n}{\log n}}\) 時，總復雜度有最小值 \(O(m\sqrt{\log n\log\log n})\)。此時，在 \(m=O(n)\) 的情形下，我們已經可以比普通的 \(\text{Dijkstra}\) 算法優秀了。

非常數度圖

可以看到之前的算法的瓶頸在于三度化之后有 \(O(m)\) 個點，但是其實可以不要求一個點的度數為 \(O(1)\)，把約束放寬到 \(\forall v\in V,\deg v\le k\)，重新分析復雜度。

首先，我們還是要重新建圖，此處復雜度為 \(O(m)\)，但是新圖只會有 \(O(\frac mk)\) 個點。

接著需要求解所有的 \(\text{Ball}\) 和 \(\text{Bundle}\)，這里的堆中會有 \(|S_v|k\) 個點，但是只會彈出堆頂 \(|S_v|\) 次，使用合適的數據結構（比如 \(\text{fib}\) 堆）可以做到 \(O(\sum_{v\in V} |S_v|k+|S_v|\log(|S_v|k)=O(m+\frac mk\log m)\) 的復雜度。

然后對 \(\text{Bundle}\) 間進行 \(\text{Dijsktra}\)，這里的復雜度是 \(O(k\sum_{v\not\in R}|\text{Ball}(v)|)=O(\frac mp)\)。

總的復雜度為 \(O(m+\frac mk\log m+\frac mp)\)，注意到在稀疏圖中 \(\log m=O(\log n)\)，如果取

可以得到復雜度為 \(n\sqrt{\log n\log\log n}\) 和 \(\sqrt{mn\log n}\)，