作者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