单源最短路径，每个边缘具有距离和权重 [英] Single-source shortest path with distance and weight for each edge

问题描述

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

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.

这篇关于单源最短路径，每个边缘具有距离和权重的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！