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