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

Question

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

我已经尝试过实现 Djikstra 并在我超过成本时简单地回溯(因为没有更好的术语)，直到我遍历整个图。但是，我正在寻找比这更快的解决方案。我也曾尝试使用一个函数来根据边的距离和成本创建权重，但我认为这不会返回最佳解决方案。

有什么想法吗？

Answer 1

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

因此，从起始节点 0 开始，假设我们以距离 a 和成本 b 行进到节点 1，现在，我们有距离矩阵:

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

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