分支定界算法寻找带约束的最短路径

Question

我有一个有向图 G，其中两个边属性“cost”和“toll”代表从节点 i 到 j 的不同度量。

现在我想计算从起点到终点的最短路径（最小成本）（约束收费<= max_toll), but my code's result is different with the python networkx api's (nx.dijkstra_path) result, so is there a possibile logic error in my code? Can someone help or specify the cause of the error?

这是API代码：

min_path = nx.dijkstra_path(G, 0, 49, weight="cost")

这是我的代码：

def dijkstra_with_toll_constraint(G, start, end, max_toll):
    pq = [(0, start, 0, [start])]  # (sum_cost, current_node, sum_toll, path)
    visited = set()
    while pq:
        cost, node, toll, path = heapq.heappop(pq)
        if node == end and toll <= max_toll:
            return cost, toll, path

        if node in visited:
            continue
        visited.add(node)

        for neighbor in G.neighbors(node):
            next_cost = cost + G[node][neighbor]["cost"]
            next_toll = toll + G[node][neighbor]["toll"]
            if next_toll <= max_toll:
                heapq.heappush(pq, (next_cost, neighbor, next_toll, path + [neighbor]))

    return float("inf"), float("inf"), None

Answer 1

Your implementation of Dijkstra's algorithm with toll constraint looks mostly correct. However, there's a subtle difference between your implementation and the NetworkX implementation of Dijkstra's algorithm that might be causing the discrepancy in results.

In NetworkX's implementation of Dijkstra's algorithm (nx.dijkstra_path), the algorithm continues exploring paths even after finding the destination node until it has explored all possible paths from the source to all other nodes. This ensures that the shortest path to the destination node is found.

In your implementation, once a path reaching the destination node with a toll less than or equal to the maximum toll is found, it immediately returns that path. This means that it might not necessarily find the shortest path if it exists.

To ensure that your implementation finds the shortest path with the toll constraint, you need to modify it to continue exploring paths even after finding a path reaching the destination node. Then, among all paths reaching the destination node with toll less than or equal to the maximum toll, select the one with the minimum cost.

Here's how you can modify your code to achieve this:

def dijkstra_with_toll_constraint(G, start, end, max_toll):
    pq = [(0, start, 0, [start])]  # (sum_cost, current_node, sum_toll, path)
    visited = set()
    min_cost = float('inf')
    min_path = None
    while pq:
        cost, node, toll, path = heapq.heappop(pq)
        if node == end and toll <= max_toll:
            if cost < min_cost:
                min_cost = cost
                min_path = path
            continue  # Continue exploring other paths

        if node in visited:
            continue
        visited.add(node)

        for neighbor in G.neighbors(node):
            next_cost = cost + G[node][neighbor]["cost"]
            next_toll = toll + G[node][neighbor]["toll"]
            if next_toll <= max_toll:
                heapq.heappush(pq, (next_cost, neighbor, next_toll, path + [neighbor]))

    return min_cost, min_path