...图上所有点?如果要求经过图上所有点的最短路径,应该用什么方法...

发布网友发布时间：2024-03-06 11:00

共2个回答

热心网友时间：2024-04-01 11:45

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

热心网友时间：2024-04-01 11:46

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