推 juan19283746:不久前有 01/24 15:57
推 jameschou:先對所有點做拓樸排序,再依這順序做類似Dijkstra's algo 01/24 16:57
→ privatewind:acyclic代表圖為 forest 01/24 19:03
→ privatewind:直接以起點為根做DFS就可以了 01/24 19:04
→ privatewind:只要能到達 即為最短路徑 01/24 19:18
推 cakeboy:這題好像用DAG,用toplogically做,可以在O(v+E)解決 01/24 19:21
推 hswayne:I2A有 01/24 22:38
→ dy957:bellmanford 不是O(VE)嗎 01/24 23:00
推 jameschou:是O(VE)沒錯 我猜他是因為|E|最多|V|^2 所以乾脆寫|V|^3 01/24 23:08
推 cakeboy:O(VE)會不會是搭配adgancy list O(V^3)matrix 用dijkstra 01/24 23:14
→ dy957:對吼 01/24 23:14
→ cakeboy:做n次 01/24 23:14
→ privatewind:耶~~請問一下，直接用DFS有錯嗎? 0.0 01/25 07:06
推 christianSK:如果是acyclic connected的, path應該是唯一存在吧!? 01/25 07:30
→ privatewind:樓上是的...因為是tree 01/25 07:37
→ dy957:可是acyclic ..不一定path唯一吧 可能有多個點指向同一點 01/25 11:26
→ privatewind:由a至b一定path唯一 01/25 12:26
→ privatewind:single shortest path就是解點對點的shortest path 01/25 12:26
→ privatewind:另外tree的定義就是conected and acyclic gragh 01/25 12:27
→ christianSK:恩~ 如果這樣說 就照p大講的DFS就可以了吧 01/25 12:46
→ christianSK:另外求最短路徑的問題應該都是預設connected吧 01/25 12:46
→ privatewind:沒有...shortest path通常沒有這樣的假設 01/25 12:51
→ privatewind:所以我第一次推文才說forest 01/25 12:52
推 christianSK:恩~ 了解了! 謝謝 :) 01/25 12:53
推 cakeboy:我看到的程式碼是先用拓墣排序 排出順序 再每個點依順序跑 01/25 20:18
→ dy957:但是這是有向圖,多個點指向同一個點並不違反acyclic吧 01/25 21:47
→ dy957:如果a->b->c, a->d->c 不就有兩條path了? 01/25 21:48