我需要在带有循环的加权图中找到两个节点之间最便宜和最短的路径。我正在 Prolog 中实现这个。
由于我必须找到最便宜(最便宜)和最短(最短)路径，我想我应该使用以下方法计算所有现有的可能路径带回溯的深度优先搜索，因为它的内存消耗低且相对较快(我使用辅助列表来跟踪访问过的节点以解决循环问题)，然后从收集的路径列表中选择最便宜的路径最短路径。
我排除了使用启发式算法(例如 A*)，因为虽然速度更快，但这些算法依赖于估计函数，并且在估计可能错误的某些特定情况下它们可能会给出错误的答案。我不需要一个好的解决方案，我想要最佳解决方案。
所以我的问题是:我针对这个问题给出的方法是否有意义，更具体地说，以确保我在具有循环的两个节点之间的图形问题中获得最多/最少的路径(例如最便宜的路径)，是否有意义计算所有现有的解决方案，然后通过与其他解决方案进行比较来选择正确的解决方案是有意义的，还是我以错误的方式解决这个问题？
最佳答案
这里不需要使用自定义算法。您可以只使用标准的最短路径查找算法(如果所有权重均为非负，则使用 Dijkstra 算法，否则使用 Ford-Bellman 或 Floyd 算法)。边的权重应分别是第一个问题和第二个问题的成本和距离。
关于algorithm - 两个节点之间最便宜且最短的路径，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/40952628/