鐵人檔案
圖論的應用層面有兩種，其中一種應用是把一個題目使用圖論的模型來找出其特性，並且根據這些特性設計出演算法解決該問題。另一種應用則是建立圖論模型後，使用已知的工具（比方說線性規劃、矩陣相乘等等）來解決這些已知的圖論問題。在這 30 天之中，我想要介紹一些與圖論相關的演算法問題，並且描述一些範例程式。
11 近似最短路徑 前面介紹的所有點對最短路徑演算法，好寫的得花 n^3 的時間、比較快的又得仰賴矩陣相乘。如果是單一源頭最短路徑演算法，仰賴的 BFS 或 D...
11.2 距離不超過 3 倍的 Baswana-Sen Spanner 如果我們把近似最短距離的要求再度放寬，比方說找出一個子圖 H，使得圖 H 上任兩點之間的...
11.3 一些 Leetcode 例題 再來看一些有趣的最短路徑變化題吧！ Leetcode 882. Reachable Nodes in Subdivide...
11.4 Thorup-Zwick 的 Approximate Distance Oracle 什麼是 Distance Oracle 呢？這是一種資料結構，可...
11.5 Agarwal-Godfrey 的 2 倍近似 Distance Oracle Thorup-Zwick 當年在仿真圖上面的想法，是選取許多叢集中心當...
11.6 距離標籤 Distance Labellings 最短距離資料結構 Distance Oracles 有一個非常極端的形式，那就是距離標籤：透過預處理...
11.6a 把樹合併起來 讓我們簡單描述一下把樹合併起來的過程，補上昨天 Peleg’s Distance Labelling 演算法的最後一塊拼圖。 試想一下...
今天來寫點雜記和更多的 Leetcode :) 11.7 把樹對應到 Hamming Distance 距離標籤是個有趣的概念，如果想要讓計算距離的過程更加簡化...
11.9 賦距空間與 L1 嵌入的 Bourgain 定理 圖上的距離也滿足賦距空間(metric space)的定義：非負距離、對稱性、遞移律、三角不等式。如...
12 第 k 短路徑 給一個有向無負圈圖，以及兩個點 s 和 t、還有一個正整數 k。請找出所有不同的 s-t 走訪(walk；允許重複經過點) 中總長前 k...
