→ privatewind:我錯了 我忘了 tree的acyclic 定義還有附加條件 01/26 12:37
→ privatewind:acyclic in the associative undirected gragh 01/26 12:37
推 predatorK:THX 01/27 21:26
※ 引述《predatorK (predator')》之銘言：
: 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)
跟朋友討論到這題，就來幫推文補充一下
方法跟推文的應該差不多，就是先做一個topological sort再
用類似Dijkstra's algorithm的方法去找，演算法大概是長這樣：
假設整個graph已經被topological sort過了，V(0)是起點
d(V(0)) = 0
for i = 1 to V.size()-1
d(V(i)) = INFINITE
for i = 0 to V.size()-1
for each edge E of V(i)
Let j = index of the node that is on the other side of E
if d(V(i)) + w(E) < d(V(j))
d(V(j)) = d(V(i)) + w(E)
用adjacency list很明顯time complexity是O(V+E)
這跟Dijkstra唯一的差別就是Dijkstra's algorithm會去找「離目前已經建好的
shortest path tree最近的點」，但上面的演算法沒有做這件事，而是把V(i)直
接當作那個點，為什麼可以這樣做勒？
因為當loop走到V(i)的時候，我們一定已經考慮過所有到V(i)的path了。也就是
說根據topological order的特性，所有{V(j)|j>i}一定都不會有edge連到V(i)
，也就是說d(V(i))已經不可能再更小了，既然他不可能再更小，他就一定在
shortest path tree裡面，所以loop走完shortest path tree也就建完啦
另外Dijkstra's algorithm有個限制是所有edge weight一定都要是nonnegative
，這個演算法就應該沒有，畢竟上面的推論沒有利用到這點
然後推文好像有些大大在討論是不是可以用DFS解之類的
會不會是題目上認知有些不同呢@@，如果所有的edge
weight都是1的話是可以用BFS來做沒錯啦......
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.169.161.96
※ 編輯: jimmycool 來自: 118.169.161.96 (01/26 00:47)