Finite Playground

To verify is human; to prove, divine.

Shortest paths in graphs with integral weights

Leave a comment

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


Author: hcsoso

Ph.D. student in the Department of Computer Science, University of Illinois at Urbana-Champaign.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s