Dijkstra's algorithm implementation is wrong in heapq usage

[qianzhang42]

In "Shortest Path with Dijkstra’s Algorithm", the implementation used "entry_lookup[neighbor][0] = distance" to change entry value in heap.

This will not work because heap will not reorganize after this modification. One correct way to reorganize this heap is using heapq._siftdown function. You can find some reference here.

[ozan]

Hi @qianzhang42 , thanks for catching that! Would you be interested in contributing a patch (including a test case) for it?

[qianzhang42]

Sorry for the late reply. Sure. I would love to patch this. But I am not quite familiar about the whole process. Are there any tutorial or instructions on doing this? Thanks.

[zhengzh]

What you need is the indexed priority queue which can reorganize automatically when its elements are modified. Here is the code

from pqdict import pqdict

def calculate_distances(graph, starting_vertex):
    distances = {vertex: float('infinity') for vertex in graph}
    distances[starting_vertex] = 0

    pq = pqdict({starting_vertex: 0})
    
    while len(pq) > 0:
        current_vertex, current_distance = pq.popitem()
        
        for neighbor, neighbor_distance in graph[current_vertex].items():
            distance = distances[current_vertex] + neighbor_distance
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                pq[neighbor] = distance

    return distances


example_graph = {
    'U': {'V': 2, 'W': 5, 'X': 1},
    'V': {'U': 2, 'X': 2, 'W': 3},
    'W': {'V': 3, 'U': 5, 'X': 3, 'Y': 1, 'Z': 5},
    'X': {'U': 1, 'V': 2, 'W': 3, 'Y': 1},
    'Y': {'X': 1, 'W': 1, 'Z': 1},
    'Z': {'W': 5, 'Y': 1},
}
print calculate_distances(example_graph, 'X')