[理工] [DS]99成大資工

看板Grad-ProbAsk作者 (predator')時間15年前 (2011/01/24 14:02), 編輯推噓9(9推 0噓 19→)
留言28則, 8人參與, 最新討論串1/2 (看更多)
5.(20%)Present a linear-time algorithm to solve the single shortest paths in directed acyclic graphs. 請問shortest paths要如何達到linear time呢? Dijkstra's 要O(n^2) Bellmenford 要O(n^3) -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 180.176.14.222
推
01/24 15:57, , 1F
不久前有
01/24 15:57, 1F
推
01/24 16:57, , 2F
先對所有點做拓樸排序,再依這順序做類似Dijkstra's algo
01/24 16:57, 2F
→
01/24 19:03, , 3F
acyclic代表圖為 forest
01/24 19:03, 3F
→
01/24 19:04, , 4F
直接以起點為根做DFS就可以了
01/24 19:04, 4F
→
01/24 19:18, , 5F
只要能到達 即為最短路徑
01/24 19:18, 5F
推
01/24 19:21, , 6F
這題好像用DAG,用toplogically做,可以在O(v+E)解決
01/24 19:21, 6F
推
01/24 22:38, , 7F
I2A有
01/24 22:38, 7F
→
01/24 23:00, , 8F
bellmanford 不是O(VE)嗎
01/24 23:00, 8F
推
01/24 23:08, , 9F
是O(VE)沒錯 我猜他是因為|E|最多|V|^2 所以乾脆寫|V|^3
01/24 23:08, 9F
推
01/24 23:14, , 10F
O(VE)會不會是搭配adgancy list O(V^3)matrix 用dijkstra
01/24 23:14, 10F
→
01/24 23:14, , 11F
對吼
01/24 23:14, 11F
→
01/24 23:14, , 12F
做n次
01/24 23:14, 12F
→
01/25 07:06, , 13F
耶~~請問一下，直接用DFS有錯嗎? 0.0
01/25 07:06, 13F
推
01/25 07:30, , 14F
如果是acyclic connected的, path應該是唯一存在吧!?
01/25 07:30, 14F
→
01/25 07:37, , 15F
樓上是的...因為是tree
01/25 07:37, 15F
→
01/25 11:26, , 16F
可是acyclic ..不一定path唯一吧 可能有多個點指向同一點
01/25 11:26, 16F
→
01/25 12:26, , 17F
由a至b一定path唯一
01/25 12:26, 17F
→
01/25 12:26, , 18F
single shortest path就是解點對點的shortest path
01/25 12:26, 18F
→
01/25 12:27, , 19F
另外tree的定義就是conected and acyclic gragh
01/25 12:27, 19F
→
01/25 12:46, , 20F
恩~ 如果這樣說 就照p大講的DFS就可以了吧
01/25 12:46, 20F
→
01/25 12:46, , 21F
另外求最短路徑的問題應該都是預設connected吧
01/25 12:46, 21F
→
01/25 12:51, , 22F
沒有...shortest path通常沒有這樣的假設
01/25 12:51, 22F
→
01/25 12:52, , 23F
所以我第一次推文才說forest
01/25 12:52, 23F
推
01/25 12:53, , 24F
恩~ 了解了! 謝謝 :)
01/25 12:53, 24F
推
01/25 20:18, , 25F
我看到的程式碼是先用拓墣排序 排出順序 再每個點依順序跑
01/25 20:18, 25F
→
01/25 21:47, , 26F
但是這是有向圖,多個點指向同一個點並不違反acyclic吧
01/25 21:47, 26F
→
01/25 21:48, , 27F
如果a->b->c, a->d->c 不就有兩條path了?
01/25 21:48, 27F
→
09/11 14:10, , 28F
由a至b一定path唯 https://daxiv.com
09/11 14:10, 28F
‣ 更多 predatorK 的文章
文章代碼(AID): #1DFHNSGZ (Grad-ProbAsk)
‣ 更多 predatorK 的文章
文章代碼(AID): #1DFHNSGZ (Grad-ProbAsk)