Печать пути в задаче с ограничениями на кратчайший путь (поиск с равномерной стоимостью)

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)))

Кажется, проблема в том, что я обновляю predecessorsсловарь в цикле for. Поскольку я разрешил посещать узлы более одного раза, чтобы получить решение, предшественник узла будет обновляться. И если я обновлю предшественника только в if new_dist < distances.get(neighbor, float('inf')):, напечатанный путь всегда будет кратчайшим путем для немодифицированной ПСК (т. е. даже без учета ограничения энергетического бюджета). Это будет работать в этом примерном графике, но не будет работать при использовании больших графиков, таких как тот, что был в 9-й задаче внедрения DIMACS.

Есть ли какой-нибудь подход, который я могу использовать, чтобы правильно распечатать кратчайший возможный путь, не слишком сильно изменяя исходный код в этой задаче?