作者lanniba (爛泥巴)
看板Prob_Solve
標題[問題] 路徑演算法相關的問題
時間Fri Sep 7 17:39:28 2012
想請問一下
不知道是否有相關或類似的演算法能知道
一個無向圖裡面，能夠走完每個"邊"的最短路徑(節點重複走過沒關係)
希望有大大可以給我提示@@
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 120.126.16.69
1F：推 LPH66:Euler trail 的變形問題? 09/07 17:41
2F：→ lanniba:恩恩@@ 09/07 17:42
3F：推 suhorng:Chinese Postman Problem, 我記得當一個圖沒有 Euler- 09/07 17:48
4F：→ suhorng:trial 時會需要用 weighted graph matching... 09/07 17:48
weighted graph matching@@?是再從邊的權重下手囉?
5F：→ tkcn:走過每個邊的"最短路徑"? 這樣是連邊都要重複走了吧? 09/07 21:22
恩恩，應該有可能無法一次就把每個邊都全部走完，有的邊可能要重複走
※ 編輯: lanniba 來自: 120.126.16.69 (09/07 21:56)
6F：→ suhorng:請查 Chinese Postman problem (或T-join problem...) 09/07 22:13
7F：→ suhorng:沒有Euler-circuit的話一定有很多(偶數個)奇點 09/07 22:13
8F：→ suhorng:變成要多加邊 來造出 Euler-circuit 09/07 22:14
9F：→ suhorng:弄一弄會發現求出那些奇點的 All-pair shortest path 後 09/07 22:15
10F：→ suhorng:用一般圖帶權匹配可以解決 09/07 22:15
11F：→ lanniba:感謝s大的提示 09/09 14:18