具有每条边的距离和权重的单源最短路径

Question

假设有一个无向图，连接任意两个节点的每条边都有两个权重(即距离和成本)。我希望得到最短的路径，但也要确保不超出一定的成本。

我已经尝试实现Djikstra的，如果我超过了成本，就简单地回溯(因为没有更好的术语)，直到我遍历整个图。然而，我正在寻找一种比这更快的解决方案。我还尝试使用一个函数，该函数在给定边的距离和成本的情况下创建一个权重，但我认为这不会返回最优解。

有什么想法吗？

Answer 1

我们可以将您的图从具有E边和V顶点的原始图(E,V)转换为具有每个节点的另一个图(E, V')，v'xy in V'是从起点到具有成本y的节点x的最小距离。

因此，从开始节点0开始，假设我们使用距离a和成本b到达节点1，现在，我们有我们的距离矩阵：

dist[0][0] = 0, and dist[1][b] = a;

因此，这个问题就变成了一个正常的最短路径问题。

Answer 2

取成本和距离的加权平均值并将其作为参数。

说平均值，p=w*cost+(1-w)*distance

现在根据您的成本限制选择w。

现在，在任何最短路径算法中都可以比较p。