打印约束最短路径问题中的路径（统一成本搜索）

Question

假设我们得到一个带有预定义源节点 (S) 和目标节点 (T) 的图。图中的每条边都与一对值 (X, Y) 相关联，其中 X 表示距离，Y 表示能量成本。请参阅图片进行说明：示例图（假设 S = '1'，T = '6'）

工作是找到 S 和 T 之间的最短路径，使得沿路径累积的能量成本不超过能量预算。具体来说，我们希望找到从'1'到'6'不超过能量预算17的最短路径。

我们可以观察到，虽然路径1->2->4->6的行进距离最短为3，但其累积的能量成本18超过了能量预算17。因此，该路径是不可行的。在该示例中，路径1→2→5→6是最短可行路径。

现在，我使用了稍微修改过的统一成本搜索（UCS）算法，并且能够找到最短距离和总能量成本，但我在打印最短路径本身时仍然遇到问题：

Shortest path: 1->2->4->5->6.  # Should be 1->2->5->6
Shortest distance: 5.
Total energy cost: 15.

是我尝试过的：

import heapq

# Constants
START = '1'
END = '6'
BUDGET = 17
NO_PATH = (START, 0, 0)  # Output to print if no path

# Dictionaries for graph
G = {
    '1': ['2', '3'], 
    '2': ['4', '5'], 
    '3': ['2', '4', '5'], 
    '4': ['5', '6'], 
    '5': ['6'], 
    '6': []
}

Dist = {
    '1,2': 1, 
    '1,3': 10, 
    '2,4': 1, 
    '2,5': 2, 
    '3,2': 1, 
    '3,4': 5, 
    '3,5': 12, 
    '4,5': 10, 
    '4,6': 1, 
    '5,6': 2
}

Cost = {
    '1,2': 10, 
    '1,3': 3, 
    '2,4': 1, 
    '2,5': 3, 
    '3,2': 2, 
    '3,4': 7, 
    '3,5': 3, 
    '4,5': 1, 
    '4,6': 7, 
    '5,6': 2
}

def ucs(start, goal):
    """
    Uniform cost search with energy constraint.

    Return the shortest path, distance travelled and energy consumed.
    """
    # Initialization
    pq = [(0, 0, start)]            # Min-heap priority queue (dist, cost, node)
    predecessors = {start: None}    # Dict of predecessors {node: predecessor}
    distances = {start: 0}          # Dict of distance from start to node
    costs = {start: 0}              # Dict of cost from start to node

    while pq:
        # Dequeue
        dist, cost, node = heapq.heappop(pq)

        # Return solution when goal is reached
        if node == goal:
            path = [node]
            while node != start:
                node = predecessors[node]
                path.append(node)
            return path[::-1], dist, cost

        for neighbor in G[node]:
            # Calculate new distance and cost based on current node
            new_dist = dist + Dist[','.join([node, neighbor])]
            new_cost = cost + Cost[','.join([node, neighbor])]
            if new_cost > BUDGET:
                continue
            # Return infinity as value if key not in dict (to avoid KeyError)
            # so new distance and cost will always be lower for first time visited nodes
            if new_dist < distances.get(neighbor, float('inf')) or new_cost < costs.get(neighbor, float('inf')):
                # If new distance is shorter, update distances dict
                if new_dist < distances.get(neighbor, float('inf')):
                    distances[neighbor] = new_dist
                # If new cost is lower, update costs dict
                if new_cost < costs.get(neighbor, float('inf')):
                    costs[neighbor] = new_cost
                # Assign current node as predecessor
                predecessors[neighbor] = node
                # Enqueue
                entry = (new_dist, new_cost, neighbor)
                heapq.heappush(pq, entry)

if __name__ == '__main__':
    path, distance, cost = ucs(START, END) or NO_PATH
    print('Shortest path: {}.'.format('->'.join(path)))
    print('Shortest distance: {}.'.format(str(distance)))
    print('Total energy cost: {}.'.format(str(cost)))

这 似乎问题是当我在 for 循环中更新 predecessors 字典时。由于我允许多次访问节点以获得解决方案，因此节点的前任节点将不断更新。如果我仅在 if new_dist 中更新前身distances.get(neighbor, float('inf')):，打印的路径将始终是未修改的 UCS 的最短路径（即，甚至不考虑能量预算约束）。它在此示例图中可以工作，但在使用大型图（例如第 9 届 DIMACS 实施挑战中的图）时会失败。

在这个问题中，我可以采取什么方法来正确打印出最短可行路径，而无需过多修改原始代码？