I have a directed graph G with two edge attributes “cost” and “toll” representing different metrics from node i to j.
Now I want to calculate the shortest path (minimum cost) from start to end (constraint toll <= 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?
This is the api code:
<code>min_path = nx.dijkstra_path(G, 0, 49, weight="cost")
</code>
<code>min_path = nx.dijkstra_path(G, 0, 49, weight="cost")
</code>
min_path = nx.dijkstra_path(G, 0, 49, weight="cost")
This is my code:
<code>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
</code>
<code>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
</code>
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
The The reason why the two results are different is that nx.dijkstra_path does not consider constraints (toll <= max_toll)
2