🚄 Dijkstra

Shortest Path Problem §

Find the shortest path from to all other vertices in a weighted graph with non-negative weights.

Theory §

Greedily go to the next-closest vertex , then update distances to its neighbors. If there was a shorter path to that ends with , we would’ve gone to already and found this path; therefore, the one we just found must be the shortest path.

Implementation §

from heapq import heappush, heappop
 
def dijkstra(s, adj):
	dist = [float('inf') for _ in range(len(adj)]
	dist[s] = 0
	pq = [(0, s)]
	while len(pq) > 0:
		d, c = heappop(pq)
		for n, w in adj[c]:
			if dist[c] + w < dist[n]:
				dist[n] = dist[c] + w
				heappush(pq, (dist[n], n))
	return dist

Runtime §

Priority queue takes for both push and pop. We pop each vertex once, taking total, and use each edge once to add a neighbor to the priority queue, taking total; therefore, our total runtime is .