DSA — Dijkstra's Algorithm

What is Dijkstra's Algorithm?

Finds the shortest path from a source to all vertices in a weighted graph.

import heapq

def dijkstra(graph, start):
    distances = {vertex: float('infinity') for vertex in graph}
    distances[start] = 0
    previous = {vertex: None for vertex in graph}
    pq = [(0, start)]
    
    while pq:
        current_dist, current = heapq.heappop(pq)
        
        if current_dist > distances[current]:
            continue
        
        for neighbor, weight in graph[current].items():
            distance = current_dist + weight
            
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                previous[neighbor] = current
                heapq.heappush(pq, (distance, neighbor))
    
    return distances, previous

Time Complexity

Operation	Complexity
Using priority queue	O((V + E) log V)
Using array	O(V²)

Applications

• GPS navigation
• Network routing
• Flight scheduling
• Robotics path planning

Mini Practice

1. Implement Dijkstra's algorithm
2. Find shortest path
3. Reconstruct the path
4. Handle negative weights (use Bellman-Ford)

Up Next

Continue with Floyd-Warshall — all-pairs shortest path.