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

Question

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

我尝试了实现Djikstra算法，并且在超出成本时简单地回溯（为了缺乏更好的术语），直到遍历整个图。然而，我正在寻找比这更快的解决方案。我还尝试使用一个函数，根据边的距离和成本创建一个权重，但我不认为这会返回最佳解决方案。

有什么想法吗？

- user3646937

---

这里有一个答案：https://dev59.com/8U3Sa4cB1Zd3GeqPu2d-。 - G. Bach

Answer 1

我们可以将您的图从原始图转换为具有每个节点 v'xy 的最小距离的另一个图(E，V')，以便从起点到节点 x 的旅行成本为 y。(保留html标签)

因此，从起点0开始，假设我们通过距离为a和成本为b的节点1旅行，现在我们有我们的距离矩阵：(保留html标签)

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

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

- Pham Trung

---

新的边和边权是什么？ - G. Bach

Answer 2

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

假设平均值为 p=w*cost+(1-w)*distance

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

现在在任何最短路径算法中，通过比较 p 来进行工作。

- 0x5050