Python Program to Implement Dijkstra's Algorithm

Dijkstra's algorithm finds the shortest path from a single source node to every other node in a weighted graph (as long as none of the edge weights are negative). It's the algorithm behind real routing systems — GPS navigation, network packet routing, and flight-connection search all rely on some variant of it — and it's one of the most frequently asked graph algorithms in technical interviews.

Unlike plain BFS, which finds the shortest path by number of edges in an unweighted graph, Dijkstra's algorithm accounts for edge weights (distances, costs, time) using a priority queue to always expand the closest unvisited node next.

Python Program to Implement Dijkstra's Algorithm

import heapq


def dijkstra(graph, start):
    # Initialize every node's distance to infinity, except the start node
    distances = {node: float("inf") for node in graph}
    distances[start] = 0

    # Priority queue of (distance, node) — heapq always pops the smallest first
    priority_queue = [(0, start)]
    visited = set()

    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_queue)

        if current_node in visited:
            continue
        visited.add(current_node)

        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))

    return distances


graph = {
    "A": {"B": 4, "C": 1},
    "B": {"A": 4, "C": 2, "D": 5},
    "C": {"A": 1, "B": 2, "D": 8},
    "D": {"B": 5, "C": 8},
}

shortest_distances = dijkstra(graph, "A")
for node, distance in shortest_distances.items():
    print(f"Distance from A to {node}: {distance}")

Output:

Distance from A to A: 0
Distance from A to B: 3
Distance from A to C: 1
Distance from A to D: 8

Notice the shortest path from A to B is 3 (via C: A→C→B costing 1+2), not the direct 4 — this is exactly what Dijkstra's algorithm is built to find. The heapq module gives an efficient min-priority queue so the algorithm always processes the closest unvisited node next, yielding a time complexity of O((V + E) log V) with a binary heap, where V is the number of nodes and E is the number of edges. One important caveat: Dijkstra's algorithm breaks down with negative edge weights (it can produce wrong answers), in which case the Bellman-Ford algorithm is used instead.

---