有两个条件的最短路径问题 [英] Shortest paths problem with two conditions

问题描述

假设我有一个有向图G（V，E，w，c），其中w是每条边的正权重，c是每条边的成本为1或0.我需要找到一种算法对于给定的源顶点，u查找从u到V中所有成本≤k（其中k≥1）的顶点的最短路径。

Let's say i have a directed graph G(V,E,w,c) where w is the positive weight of each edge and c is the cost of every edge being either 1 or 0.I need to find an algorithm that for given source vertice u finds the shortest paths from u to every vertice in V that have cost ≤ k(where k≥1).

我尝试修改Bellman ford算法，但我似乎找不到解决方法。

I tried modifying Bellman ford's algorithm but i can't seem to find the solution.

推荐答案

让我重申对问题的理解。

Let me restate my understanding of the problem.

对于成本不超过 k 的所有顶点，您需要从顶点 u 。

For all vertices that you can reach with a cost of no more than k, you want the path of minimal weight that gets there from a vertex u.

您需要综合考虑才能达到目标。

You need a combination of ideas to get there.

假设 RouteToNode 对象具有以下属性： cost ，权重，节点， lastRouteToNode 和自动递增的 id 。这是一个链接列表，可将我们带回到原始节点，从而使我们可以重新构造路径。我们将它们按照以下价格进行比较：成本，然后是重量，然后是 id 。

Suppose that a RouteToNode object has the following attributes: cost, weight, node, lastRouteToNode and an autoincrementing id. This is a linked list carrying us back to the original node, letting us reconstruct the route. We compare them by cost, then weight, then id.

我们有一个哈希/字典/无论您要调用什么，它将节点映射到权重最低的 RouteToNode 对象到达该节点。称之为 bestRoute 。

We have a hash/dictionary/whatever you want to call it that maps nodes to the lowest weight RouteToNode object reaching that node. Call it bestRoute.

我们有一个待办事项列表具有尚未处理的 RouteToNode s的优先级队列，该队列始终返回最小的 RouteToNode 。请注意，它总是从最低成本返回最高成本。

We have a todo list that has RouteToNodes that we have not yet processed which is a priority queue that always returns the minimal RouteToNode. Note that it always returns them from lowest cost to highest.

我们从 bestRoute 开始，一个只有单个 RouteToNode 的 todo 队列，即：

We start with bestRoute having nothing in it, and a todo queue with only a single RouteToNode, namely:

{
    id: 0,
    cost: 0,
    weight: 0,
    node: u,
    lastRouteToNode: null
}

现在我们执行以下伪代码：

And now we execute the following pseudocode:

while todo is not empty:
    thisRouteToNode = todo.pop()
    if thisRouteToNode.node not in bestRoute or
      thisRouteToNode.weight < bestRoute[thisRouteToNode.node].weight:
        bestRoute[thisRouteToNode.node] = thisRouteToNode
        for edge adjacent to thisRouteToNode.node:
            construct nextRouteToNode by adding edge
            if nextRouteToNode.cost <= k:
                todo.push(nextRouteToNode)

这篇关于有两个条件的最短路径问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！