dijkstra's algorithm

A greedy algorithm for finding the shortest path in a weighted graph. In short:

• go to nearest
• update nearest’s neighbours if shorter path is through nearest, add neighbour to queue

Steps:

• create an adjacency list for the graph
• create a dict to store min distances
  • to source: 0
  • to all other nodes: infinite
• create a min heap to store vertices by their current shortest distance from the source
• while the heap is non-empty:
  • pop to visit the node with the minimum distance
  • visit its neighbours
    • if the current distance + the edge weight < the known distance to that vertex, update the distance and the heap

def dijkstra(graph, V, src):
    dist = [float('inf')] * V
    dist[src] = 0
    pq = [(0, src)]  # (distance, vertex)
    
    while pq:
        current_dist, u = heapq.heappop(pq)
        
        if current_dist > dist[u]:
            continue
        
        for neighbor, weight in graph[u]:
            distance = current_dist + weight
            
            if distance < dist[neighbor]:
                dist[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))
    
    return dist
 
# Example usage
graph = {
    0: [(1, 4), (2, 1)],
    1: [(3, 1)],
    2: [(1, 2), (3, 5)],
    3: []
}
V = 4
src = 0
print(dijkstra(graph, V, src))