[問題] directed graph找shortest path
看板Prob_Solve (計算數學 Problem Solving)作者mqazz1 (無法顯示)時間13年前 (2011/12/22 19:17)推噓4(4推 0噓 12→)留言16則, 3人參與討論串1/1
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
推
12/22 19:52, , 1F
12/22 19:52, 1F
→
12/22 19:52, , 2F
12/22 19:52, 2F
可是轉成i條edges 這些edges還是directed edge嗎?
轉了之後要怎麼在O(V+E)內解single shortest path呢?
→
12/22 19:54, , 3F
12/22 19:54, 3F
→
12/22 19:54, , 4F
12/22 19:54, 4F
→
12/22 19:55, , 5F
12/22 19:55, 5F
→
12/22 19:59, , 6F
12/22 19:59, 6F
可以請問shortest path跟longest path的遞迴式要怎麼寫嗎@@?
→
12/22 20:15, , 7F
12/22 20:15, 7F
→
12/22 20:16, , 8F
12/22 20:16, 8F
推
12/23 05:32, , 9F
12/23 05:32, 9F
→
12/23 05:32, , 10F
12/23 05:32, 10F
→
12/23 05:33, , 11F
12/23 05:33, 11F
推
12/23 11:21, , 12F
12/23 11:21, 12F
→
12/23 11:21, , 13F
12/23 11:21, 13F
→
12/23 11:22, , 14F
12/23 11:22, 14F
推
12/23 11:28, , 15F
12/23 11:28, 15F
※ 編輯: mqazz1 來自: 140.118.110.186 (12/25 21:51)
→
12/28 19:34, , 16F
12/28 19:34, 16F
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
-1
12
