我需要在有向、加权、循环图上找到节点 a 和 b 之间的最便宜路径，最便宜定义为从给定的任意给定引出最小返回值代价函数。通常 Djikstra 是我认为的最佳选择，除了 costfunc 采用整个路径 - 添加单个节点的效果未知(我想我可以运行costfunc 有和没有给定节点并使用差异...)。
我该怎么做？
最佳答案
没有对 costfunc 的一些限制，你不能比尝试每条可能的路径做得更好。假设
costfunc = 1 / (sum of edge weights)
那么你的问题(在循环图上)是 NP hard Longest Path Problem .
为了
costfunc =
sum of edge weights if path length = N
infinity otherwise
你有众所周知的 NP 完整 Travelling salesman problem
关于添加节点的效果未知时寻找最便宜路径的算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/30017082/