CODEWITHSUNDEEP
pythonalgorithmgraph-algorithmpriority-queuedijkstra
Arjun
Arjun

Reputation: 19

Can this code be modified to make the priority queue decrease its key in O(logn) time?

Trying to write dijkstras in python. How do I implement the decrease key operation in O(logn) when I can't modify my tuples?

I'm writing a snippet to solve dijkstras on an adjacency list and require a priority queue implementation. I'm currently passing a tuple of (priority, value) to the pq so heapify handles the push and pop for me. However, I can't modify tuples so I can't efficiently decrease the priority of any item and have to pop all items till my required one is found, then readd all items to the pq, which makes the time complexity O(V^2). Is there any way to modify this code so the decreaseKey operation works in O(logn) time? Preferably no classes involved. I can't use lists instead of tuples; it wouldn't heapify otherwise

def decrease_key(pq, v, val):
    li = []
    u = heapq.heappop(pq)

    while u[1] is not v:
        li.append(u)
        u = heapq.heappop(pq)

    for l in li:
        heapq.heappush(pq, l)

    heapq.heappush(pq, (val, v))


def dijkstra(G, src, dist, V):

    for v in range(V):
        dist[v] = float('inf')
    dist[src] = 0

    pq = []

    for k, v in dist.items():
        pq.append((v, k))

    while pq:
        u = heapq.heappop(pq)[1]
        for v, w in G[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                decrease_key(pq, v, dist[v])

O(n^2) vs required O(nlogn)

Upvotes: 0

Views: 714

Answers (2)

Kevin Pielacki
Kevin Pielacki

Reputation: 41

It's been a while but I think the point of the heap is to keep a queue of the minimum distance nodes to recalculate and update your distances.

import heapq

def dijkstra(graph, src):
    # Read all graph nodes
    nodes = list(graph.keys())

    # Initialize all distances to infinity and build a queue of unvisted nodes
    dist = {}
    pq = []
    for node in nodes:
        dist[node] = float('inf')
    dist[src] = 0
    heapq.heappush(pq, (0, src))

    # While shorter distances to nodes, recalculate neighbor distances
    while pq:
        src_dist, unvisited_node = heapq.heappop(pq)

        # Recalculate total distance for each neighbor
        unvisted_neighbors = graph.get(unvisited_node, [])
        for n_node, n_dist in unvisted_neighbors:
            test_dist = src_dist + n_dist

            # If test distance is shorted, update and enqueue
            if test_dist < dist[n_node]:
                dist[n_node] = test_dist
                heapq.heappush(pq, (test_dist, n_node))

    return dist

test_graph = {
    'a': (('b',  7), ('c',  9), ('f', 14)),
    'b': (('a',  7), ('d', 15), ('c', 10)),
    'c': (('a',  9), ('b', 10), ('d', 11), ('f',  2)),
    'd': (('b', 15), ('c', 11), ('e',  6)),
    'e': (('d',  6), ('f',  9)),
    'f': (('c',  2), ('e',  9))
}
'''Lazy graph structure.

key: source node name
value: adjacent node name and distance pairs

https://www.bogotobogo.com/python/images/Graph/graph_diagram.png
'''
src_node = 'e'
d = dijkstra(test_graph, src_node)
for k, v in d.items():
    print(f'{src_node}->{k}: {v}')

Upvotes: 0

Matt Timmermans
Matt Timmermans

Reputation: 59293

As @DavidEisenstat indicates in comments, you don't need decrease_key if you just add multiple records to the heap.

You also need to keep track of which nodes you've popped off the priority queue, so you can only process a node the first time you see it. (Otherwise the worst case complexity increases)

And finally, it's nice if you avoid pushing those infinite costs into the heap, and if you only push a new node when you actually lower the cost. All together, something like this:

def dijkstra(G, src, dist, V):

    for v in range(V):
        dist[v] = float('inf')
    dist[src] = 0

    pq = [(0,src)]
    seen = [False]*V

    while pq:
        u = heapq.heappop(pq)[1]
        if seen[u]:
            continue
        seen[u] = True
        for v, w in G[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush( pq, (dist[v],v) )

Upvotes: 2

Related Questions