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