我需要在有向、加权、循环图上找到节点a和b之间最便宜的路径，最便宜的定义是从给定的任意costfunc中获取最小的返回值。通常情况下，djikstra是我认为最好的选择，除了costfunc走的是一条完整的路径-添加单个节点的效果是未知的（我想我可以只运行costfunc而不运行给定的节点并使用差异…）。
我该怎么办？
最佳答案
如果没有对costfunc的一些限制，你就不能做得比尝试所有可能的路径更好假设
costfunc = 1 / (sum of edge weights)
那么你的问题（在循环图上）是NP-hardLongest Path Problem。
为了
costfunc =
sum of edge weights if path length = N
infinity otherwise
你已经知道NP完全Travelling salesman problem