距離的意思
路網可能有負邊成本,例如某次轉換給予回扣。依賴非負權重的貪心最短路徑論證便可能失效。我們改以受限邊數構造最佳行走,並另外偵測何時可達負環能重複經過,使有限最小值不存在。
定義 4.2.1
(行走距離與負環)
設 是有限有向圖,有 個頂點、 條邊、每條邊 的有限實數權重 和源點 ;允許不同權重的平行邊及自環。行走可重複頂點和邊。從 到自身的空行走權重為零。每個頂點的距離定義為所有源點至該頂點行走權重的下確界;若沒有行走,記作 。負環是總權重為負的有向環(除端點外不重複頂點的閉行走;自環也算)。
若某頂點可由源點可達的負環走到,其距離是 :先繞環任意多次,再走到該點即可。這不表示某條有限行走的權重等於 。
反例模式
遇到負邊,確定最近頂點的做法會失敗
取權重 的邊 、權重 的邊 ,以及權重 的邊 。在非負權重下適用的貪心規則會先確定最近的頂點 ,距離為 ,因為其他行走都似乎是以不短於它的一段開始。但行走 的權重是 ,所以到 的真正距離是 ,先前確定的值是錯的。「之後的邊不能縮短已確定頂點的距離」這個論證需要非負權重。下面的按邊數遞推不會提早確定任何頂點:依 次序,,而 。
按邊數動態規劃
定義 4.2.2
(邊數受限的距離)
令 為由 到 使用至多 條邊的行走之最小權重;若不存在則為 。初始化 ,並對 設 。
命題 4.2.3
(按邊數的遞推式)
對 ,
空的內層最小值為 ,而 加有限權重仍為 。
證明
(在最後一條邊處拆開行走)
由 到 、至多 條邊的行走,要麼至多有 條邊,貢獻 ;要麼恰有 條邊,並以邊 結尾。後一種情況下, 之前的部分是由 到 、至多 條邊的行走,其權重至少為 ,因此整條行走的權重至少為 。所以右邊是每個候選的下界。反過來,把任何邊 接在達到 的、至多 條邊的行走之後,得到一條至多 條邊的有效行走,所以右邊的每一項都由真實的行走達到。有限圖中邊數受限的行走只有有限多條,因此每個有限最小值都會被達到。從基礎行 開始對 作歸納,即證明遞推式精確算出每個 。
使用前一行及下一行兩個陣列:先複製前一行,然後掃描每條邊,但只讀取前一行的值。這使其含義不依賴邊的掃描次序。
命題 4.2.4
( 輪之後的有限距離)
若沒有源點可達的負環能走到 ,則到 的距離等於 ;當 可達時它是有限的,否則為 。
證明
(刪去非負的環,只剩簡單路徑)
在此假設下,每條源點至 的行走上,所有環的權重均非負。從行走中刪去一個環不會增加權重,重複刪除便剩下至多 條邊的簡單路徑。因此對所有行走取的下確界,等於對至多 條邊的行走取的最小值,即 ,並且會被達到。不可達的 沒有行走,保持 。這是針對 的條件:其他地方有負環,不代表所有距離都無下界。
偵測及傳播負環影響
定理 4.2.5
(額外一輪與受影響頂點)
算出 後再同步掃描一輪得到 。存在源點可達負環,當且僅當至少一個頂點滿足 。令 為所有這類頂點,則能從 到達的頂點恰好是距離為 的頂點。
證明
(改進迫使有環,有負環也迫使有改進)
一方面,若 ,見證改進的最小行走必有 條邊,故重複某個頂點。若行走上的每個環均非負,刪掉一個環便得到至多 條邊且權重不更大的行走,矛盾。因此某個可達負環能走到 。
另一方面,可達環的每個頂點都有至多 條邊的簡單源點路徑,所以 有限。若某個可達負環上的頂點在額外一輪全沒有改善,則對每條環邊 ,遞推式給出 。沿環求和會迫使總權重非負,矛盾。因此每個可達負環至少有一個頂點屬於 。從 所有頂點出發的圖遍歷,恰好標記可在這類環之後到達的頂點。不可達負環的前驅值保持 ,不會造成改進。
證明透視
額外一輪的證明在哪裏轉折
不明顯的一步是沿環的疊加求和。沒有改進,就表示沿環的每條邊都已有不等式 ;把這些不等式相加,所有 值互相抵銷,剩下 。這個抵銷之所以合法,是因為可達環上的每個值都是有限的,所以證明先為環上每個頂點記下有限的 。在不可達的環上,各值是 ,不等式 不帶任何資訊,而那裏的負環也確實從不會被偵測到。
另一個假設是數目 :有 條邊的行走經過 個頂點,因此必定重複某個頂點,而這個重複就是可以被剪掉的環。這就是為何檢驗要看 條邊的行走:至多 條邊的行走可以是簡單路徑,完全不含環。這一輪必須是同步的,因為證明把 讀作關於至多 條邊的行走的陳述。全文也假設權重有限,因為上面的抵銷需要實數的和。
逐輪例子
例題 4.2.6
(有負邊但沒有負環)
取頂點 ,邊為權重 的 、權重 的 、權重 的 、權重 的 、權重 的 。依 次序,各行是
額外一行 不變。到 的最佳行走為 ,權重 。允許負邊;單有負邊不等於有負環。
例題 4.2.7
(只有額外一輪才揭示的負環)
取頂點 ,邊為權重 的 、權重 的 、權重 的 和權重 的 。環 的權重是 。依 次序,同步各行是
此時 ,額外一行是 ,而 ,所以 。頂點 與 在這一輪沒有改進,但兩者都能從 到達,因此遍歷把 都標記為距離 。源點保持 ,因為沒有邊回到它。
例題 4.2.8
(單一頂點與自環)
取 ,只有源點 。此時 ,額外一輪是 。若 有權重 的自環,則 ,所以偵測到該環, 的距離為 。若自環的權重為 或任何正數,則 ,不報告負環,距離為 。零權重的環不是負環,不會影響有限性。
反例模式
可達負環只影響其後繼
令 權重為 , 為 , 為 , 為 。環 權重為 ,故 的距離為 。若沒有邊回到 ,它的距離仍為 。孤立頂點 不可達,距離是 ;不可達負環也不能影響源點距離。
常見錯誤
(只報告最後一行而沒有做額外一輪)
經過 輪後,表中每個值看來都像有限的答案,但負環仍可能藏在裏面。在上面的負環例子中, 看似一張有效的最短距離表,可是到 的真正距離全都是 。只有把 與 比較,才會顯示出來。
常見錯誤
(把原地更新的陣列當作按邊數的一行)
若第一個例圖的邊按 、、 的次序掃描,並把更新寫回同一個陣列,那麼一輪之後 的值已經是 ,但 :更新在一輪中走過了三條邊。原地掃描仍然會收斂,可是它的值不能解讀為至多 條邊的距離,所以額外一輪的檢驗必須比較真正同步的各行。
成本與範圍
命題 4.2.9
(按邊數算法的運算數)
算出 並標記受影響頂點,需要 次算術及比較運算,以及輸入圖以外的 工作空間。
證明
(先數輪數,再加上一次遍歷)
一輪同步計算複製 個值並掃描 條邊,成本為 。算至 共有 輪,合共 。兩個距離陣列需要 額外空間。以鄰接表從 向前遍歷需 ,不改變上界。若保存每行以重建邊數受限的行走,則需更多空間。這是把實數算術視為常數成本的運算數,不是任意編碼下的位元複雜度保證。
練習
快速檢查
(在第一個例圖中,為何 而 ?)
數一數到 的各條路線各用幾條邊。
解答 · 答案
至多兩條邊時, 的成本是 ;更便宜的 成本是 ,但需三條邊。
快速檢查
(若 的權重為 ,而 有權重 的自環,則 的距離是多少?為甚麼?)
自環也是一個環。
解答 · 答案
為 :到達 後可任意重複自環,使行走權重無下界下降。
快速檢查
(負環不可由 到達;這件事本身會否令源點距離變成 ?)
想想源點行走能否進入該環。
解答 · 答案
不會。源點行走無法進入該環,因此無法在源點至某頂點的行走上重複它。
快速檢查
(若要把額外一輪解讀為 ,為何應使用新陣列?)
想想原地寫入會對同一輪中之後的邊產生甚麼影響。
解答 · 答案
原地更新可能在一輪中依邊次序傳過多條邊;分開陣列才能保證證明所用的至多 條邊遞推。