[問題] directed graph找shortest path

[mqazz1 (無法顯示)]

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
推 springman:BFS 可以直接在 directed graph 上做，不必轉
→ springman:將長度為 i 的 edge 轉成 i 條 edges 可能就可以
可是轉成i條edges 這些edges還是directed edge嗎?
轉了之後要怎麼在O(V+E)內解single shortest path呢?
→ springman:是 multistage graph 不是 multigraph ...
→ springman:看起來 shortest path 與 longest path 的做法類似
→ springman:有長度為負數的邊時應該也可以，因為沒有 cycle
→ firejox:這不就是DAG 用DP就好了呀
可以請問shortest path跟longest path的遞迴式要怎麼寫嗎@@?
→ firejox:DP(v1) = max/min(DP(v1), DP(v2)+weight) //v1->v2
→ firejox:max 是longest path ,min是shortest path
謝謝 因為我看解答好像不是很懂 http://ppt.cc/cVIa
紅字框起來的地方好像說要backwardly
照解答這樣..是不是應該這樣寫 L[1,j] = wi + L[i,j] ?
推 springman:因為每條邊的長度最多是 5，所以將長度為 i 的邊
→ springman:轉成 i 條邊之後，邊數最多是 5|E| 條
→ springman:代入 BFS 一樣是 O(V+E) 的時間內可以做完
推 DJWS:1. 一條邊，權重是5，就直接拆成4個點+5條邊。再跑BFS即可。
→ DJWS:就算每條邊都拆，最後也才5V點 5E邊，時間複雜度仍是O(V+E)
第一題 好像是I2A二版的習題24.3-5跟24.3-6的改版
網路上的解法 http://ppt.cc/uxY9 可是我看不太懂它的G'是什麼@@
→ DJWS:2. 請參考 activity on edge network，用DP解。
推 DJWS:對了忘記說  directed/undirected graph本來就都可以執行BFS
※ 編輯: mqazz1          來自: 140.118.110.186      (12/25 21:51)
→ DJWS:它的G'就是一條邊長度L變成L條邊長度一  只是寫的很文言而已