algorithm - 有两个条件的最短路径问题

假设我有一个有向图g（v，e，w，c），其中w是每条边的正权，c是每条边的代价是1或0。我需要找到一个算法，对于给定的源垂直，u找到从u到v中的每条垂直的最短路径，其代价小于k（其中k≥1）。
我试图修改贝尔曼福特的算法，但似乎找不到解决办法。

最佳答案

让我重申我对这个问题的理解。
对于成本不超过k的所有顶点，需要从顶点u到达的最小权重路径。
你需要各种想法的结合才能达到目的。
假设RouteToNode对象具有以下属性：cost，weight，node，lastRouteToNode和自动递增id。这是一个链接列表，将我们带回原始节点，让我们重建路由。我们通过cost，然后weight，然后id来比较它们。
我们有一个hash/dictionary/任何您想调用的名称，它将节点映射到到达该节点的最小权重RouteToNode对象称之为bestRoute。
我们有一个todo列表，其中包含尚未处理的RouteToNodes，这是一个始终返回最小RouteToNode的优先级队列。请注意，它总是从最低成本返回到最高成本。
我们从bestRoute中没有任何内容开始，而todo队列中只有一个RouteToNode，即：

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

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

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)