討論串[請益] TWO Shortest Paths
共 15 篇文章
內容預覽:
ok, 考慮以下graph,. 100. s1---------->t1 <---. / \1 \ \. S/ x------- \T /. \ \ / /. \ \ / /. s2---------->t2 /. \ 100 /. \ /. y-----------. 怕這圖不清楚, 再用文字說明
(還有139個字)
內容預覽:
ok, 找到一個方法可以把 disjoint connecting paths (#path = 2). reduce 成 two paths shortest path.. 簡單來說, 把單一點變成兩個, 中間加一條 edge 即可:. 對每個 node x, 以 x_i, x_o 取代,. 對每
(還有308個字)
內容預覽:
OK, 我搞笑了, 書沒看仔細 XD. #PATH=2 時 disjoint connecting paths 是有 polynomial time solution 的 XD. 以下是書上給的 reference,. http://historical.ncstrl.org/litesite-da
(還有362個字)
內容預覽:
感謝大家對這個問題所提供的寶貴意見，我將目前的討論串先做個整理。. (順便賺點P幣...XD). Problem A:. 給一個無向圖 G = (V, E)，. 請試著在圖上找兩條 edge-disjoint minimum weight shortest paths。. 一條由給定的起點 S1 到
(還有2349個字)