Finite Playground

To verify is human; to prove, divine.

Tag Archives: Shortest-paths


by Leave a comment

Shortest paths in graphs with integral weights

發現每次寫文章都因為希望講完整, 寫的很長因此很花時間, 久了就開始懶了.
因此, 新增一個 “速記” 分類, 用來記錄一些想要寫下來但不想整理的東西 XDD

—

目前看到在 integral weights 上解 Shortest paths 的方法有:
Thorup ’03, directed graphs, O(m + n \log\log n), by integral priority queue
Thorup ’99, undirected graphs, O(m), by hierarchical bucketing.

如果有最大的邊重 C, 那麼
van Emde Boas ’77, O(m \log\log C),
Thorup ’03, O(m + n \log\log C).

Survey: Zwick ’01.