[問題] 路徑演算法相關的問題

[lanniba (爛泥巴)]

想請問一下

不知道是否有相關或類似的演算法能知道

一個無向圖裡面，能夠走完每個"邊"的最短路徑(節點重複走過沒關係)

希望有大大可以給我提示@@

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 120.126.16.69
推 LPH66:Euler trail 的變形問題?
→ lanniba:恩恩@@
推 suhorng:Chinese Postman Problem, 我記得當一個圖沒有 Euler-
→ suhorng:trial 時會需要用 weighted graph matching...
weighted graph matching@@?是再從邊的權重下手囉?
→ tkcn:走過每個邊的"最短路徑"? 這樣是連邊都要重複走了吧?
恩恩，應該有可能無法一次就把每個邊都全部走完，有的邊可能要重複走
※ 編輯: lanniba         來自: 120.126.16.69        (09/07 21:56)
→ suhorng:請查 Chinese Postman problem (或T-join problem...)
→ suhorng:沒有Euler-circuit的話一定有很多(偶數個)奇點
→ suhorng:變成要多加邊 來造出 Euler-circuit
→ suhorng:弄一弄會發現求出那些奇點的 All-pair shortest path 後
→ suhorng:用一般圖帶權匹配可以解決
→ lanniba:感謝s大的提示