假设有一个无向图,并且连接任意两个节点的每个边都有两个权重(即距离和成本)。我想获得最短的路径,但还要确保我不会超出一定的成本。
Suppose there's an undirected graph and each edge that connects any two nodes has two weights (i.e. distance and cost). I want to get the shortest path, but also make sure I do not go beyond a certain cost.
我尝试实现Djikstra的方法,只是回溯(因为缺少如果我超出成本,则可以遍历整个图表。但是,我正在寻找比这更快的解决方案。我也尝试使用给定边的距离和成本来创建权重的函数,但我认为这不会返回最佳解决方案。
I've tried implementing Djikstra's and simply backtracking (for lack of a better term) if I exceed the cost, until I traverse the entire graph. However, I'm looking for a faster solution than this. I've also attempted to use a function that creates a weight given the distance and cost of an edge, but I don't think this will return the optimal solution.
有什么想法吗?
推荐答案我们可以使用 E 边和 V 顶点(E,V)到另一个图(E,V '),其中每个节点 v'xy 在 V'中是旅行的最小距离从起点到节点 x ,成本为 y 。
We can convert your graph from the original graph with E edges and V vertices (E,V) to another graph (E, V') with each node v'xy in V' is the minimum distance to travel from start to node x with cost y.
因此,从起始节点0开始,假设我们以距离a和成本b到达节点1,现在,我们有了距离矩阵:
So, starting at the start node 0, assuming that we travel to node 1 with distance a and cost b, now, we have our distance matrix:
dist[0][0] = 0, and dist[1][b] = a;因此,此问题成为正常的最短路径问题。
Thus, this problem become a normal Shortest path problem.
更多推荐
单源最短路径,每个边缘具有距离和权重
发布评论