Tha*_*eeb 5 c++ algorithm graph-theory cycle shortest-path
我需要一个来自一个节点的有向循环图的最短路径的示例(它应该从将作为输入的节点到达图的所有节点).
如果有一个例子,我需要用C++或算法.
编辑:哎呀,误读了这个问题.谢谢@jfclavette选择了这个.老答案结束了.
您尝试解决的问题称为旅行商问题.有许多潜在的解决方案,但它是NP完全的,所以你将无法解决大型图形.
老答案:
你想要找到的东西叫做图的周长.它可以通过设置从节点到自身的距离到无穷大并使用Floyd-Warshall算法来解决.然后,来自节点i的最短周期的长度就是位置ii中的条目.
| 归档时间： |
|
| 查看次数： |
14304 次 |
| 最近记录： |