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