弗洛伊德算法能不能经过图上所有点?如果要求经过图上所有点的最短路径,应该用什么方法?

Question

如题所述

Answer 1

floyd是求任意两点之间的最短距离。要经过所有点的话可以用蚁群算法，模拟退火算法，遗传算法。追问

谢谢!
如果再加一个条件:连接各点时,下一条路径的起点必须是上一条路径的终点,必须首尾相接,但可以返回,可以经过已经走过的路径.请问能用什么方法?

追答

这不是用什么方法，方法还是那个方法，看你怎么编程序。

Answer 2

我不得不告诉您，这个问题很有可能不存在多项式时间复杂度的算法。
如果您的问题在多项式时间内可解的话……，那么，选定图G中一点A，找出令（由B到A的边权值+从A开始经过所有点到B的最短路径长）最小的B点，您就在多项式时间内解决了货郎担问题！
然而货郎担问题是一个NP问题。所以您的问题就别指望能快速解出了……。
解决这个问题的实际算法一般都是不保证结果最优的(比如遗传算法)。要是您要保证结果最优的话，不妨去搜一下货郎担问题的算法（会比无脑搜索快一点）。本回答被网友采纳