algorithm - 两个节点之间的最便宜和最短路径

Question

我需要在带循环的加权图中找到两个节点之间最便宜和最短的路径。我正在 Prolog 中实现它。

因为我必须找到cheapest(最便宜)和shortest(最短)路径，所以我想我应该通过使用计算所有现有的可能路径带回溯的深度优先搜索，因为它的内存消耗低且相对较快(我使用辅助列表来跟踪访问过的节点以解决循环问题)，然后从收集的路径列表中选择最便宜和最短路径。

我排除了使用启发式算法(例如 A*)的可能性，因为虽然速度更快，但这些算法依赖于估计函数，并且它们可能会在估计可能错误的某些特定情况下给出错误答案。我不想要好的解决方案，我想要最好的解决方案。

所以我的问题是:我对这个问题给出的方法是否有意义，更具体地说，是为了确保我在两个有循环的节点之间的图形问题中得到最多/最少的东西(例如最便宜的)路径，是否计算所有现有解决方案然后通过与其他解决方案进行比较来选择正确的解决方案是有意义的，还是我以错误的方式解决了这个问题？

Answer 1

这里不需要使用自定义算法。您可以只使用标准的最短路径查找算法(如果所有权重都是非负数，则使用 Dijkstra，否则使用 Ford-Bellman 或 Floyd)。边的权重应该分别是第一个和第二个问题的成本和距离。