作者mqazz1 (無法顯示)
站內Prob_Solve
標題[問題] directed graph找shortest path
時間Thu Dec 22 19:17:54 2011
We have a directed graph G = (V, E) represented using adjacency lists. The
edge costs are integers in the range {1, 2, 3, 4, 5}. Assume that G has no
self-loops or multiple edges. Design an algorithm that solves the
single-source shortest path problem on G in O(|V|+|E|).
請問這怎麼把這個directed graph轉成undirected graph再套BFS解呢?
==================
還想請問一個multigraph的shortest跟longest path的問題..
http://ppt.cc/R1,B
請問這兩題應該怎麼解呢?
謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.118.110.186
1F：推 springman:BFS 可以直接在 directed graph 上做，不必轉 12/22 19:52
2F：→ springman:將長度為 i 的 edge 轉成 i 條 edges 可能就可以 12/22 19:52
可是轉成i條edges 這些edges還是directed edge嗎?
轉了之後要怎麼在O(V+E)內解single shortest path呢?
3F：→ springman:是 multistage graph 不是 multigraph ... 12/22 19:54
4F：→ springman:看起來 shortest path 與 longest path 的做法類似 12/22 19:54
5F：→ springman:有長度為負數的邊時應該也可以，因為沒有 cycle 12/22 19:55
6F：→ firejox:這不就是DAG 用DP就好了呀 12/22 19:59
可以請問shortest path跟longest path的遞迴式要怎麼寫嗎@@?
7F：→ firejox:DP(v1) = max/min(DP(v1), DP(v2)+weight) //v1->v2 12/22 20:15
8F：→ firejox:max 是longest path ,min是shortest path 12/22 20:16
謝謝 因為我看解答好像不是很懂
http://ppt.cc/cVIa
紅字框起來的地方好像說要backwardly
照解答這樣..是不是應該這樣寫 L[1,j] = wi + L[
i,j] ?
9F：推 springman:因為每條邊的長度最多是 5，所以將長度為 i 的邊 12/23 05:32
10F：→ springman:轉成 i 條邊之後，邊數最多是 5|E| 條 12/23 05:32
11F：→ springman:代入 BFS 一樣是 O(V+E) 的時間內可以做完 12/23 05:33
12F：推 DJWS:1. 一條邊，權重是5，就直接拆成4個點+5條邊。再跑BFS即可。 12/23 11:21
13F：→ DJWS:就算每條邊都拆，最後也才5V點 5E邊，時間複雜度仍是O(V+E) 12/23 11:21
第一題 好像是I2A二版的習題24.3-5跟24.3-6的改版
網路上的解法
http://ppt.cc/uxY9 可是我看不太懂它的G'是什麼@@
14F：→ DJWS:2. 請參考 activity on edge network，用DP解。 12/23 11:22
15F：推 DJWS:對了忘記說 directed/undirected graph本來就都可以執行BFS 12/23 11:28
※ 編輯: mqazz1 來自: 140.118.110.186 (12/25 21:51)
16F：→ DJWS:它的G'就是一條邊長度L變成L條邊長度一 只是寫的很文言而已 12/28 19:34