Learn how Dijkstra's algorithm finds the shortest path in a weighted graph, and how it differs from BFS.

Shortest Path

BFS finds the shortest path in an unweighted graph — where every edge counts equally. But real-world graphs are usually weighted — roads have different lengths, flights have different costs. For these, BFS does not work. Dijkstra's algorithm is the standard solution.

Dijkstra's AlgorithmA → D shortest path

current shortest distances from A

∞

dijkstra.py

def dijkstra(graph, start):

distances = {v: inf for v in graph}

distances[start] = 0

heap = [(0, start)]; visited = set()

dist, vertex = heappop(heap) # closest

for neighbor, weight in graph[vertex]:

new_dist = dist + weight

if new_dist < distances[neighbor]:

distances[neighbor] = new_dist

Start Dijkstra from A. distances = {A:0, B:∞, C:∞, D:∞}

step 0/10

Why BFS fails on weighted graphs

BFS assumes every edge costs the same — "1 step." It would treat a direct 100-mile road the same as a winding 3-mile road, simply because both are "1 edge." Dijkstra's algorithm instead tracks the actual accumulated distance to each vertex and always expands the closest unvisited vertex next.

BFS sees this as 1 hop:        Dijkstra sees this as cost 100:
   A --(100 miles)--> B           A --(100)--> B

BFS sees this as 1 hop:        Dijkstra sees this as cost 3:
   A --(3 miles)--> C             A --(3)--> C

BFS treats both paths as equal. Dijkstra correctly prefers the cheaper one.

How Dijkstra's algorithm works

Set distance to the start vertex as 0, and every other vertex as infinity
Use a min-heap (priority queue) to always process the closest unvisited vertex next
For each neighbor, calculate the distance through the current vertex
If that distance is shorter than the neighbor's current known distance, update it
Repeat until every vertex has been processed

import heapq

def dijkstra(graph, start):
    """
    graph format: {vertex: [(neighbor, weight), ...]}
    """
    distances = {vertex: float("inf") for vertex in graph}
    distances[start] = 0

    # min-heap of (distance, vertex) — always pop the closest
    heap = [(0, start)]
    visited = set()

    while heap:
        current_dist, current = heapq.heappop(heap)

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

        for neighbor, weight in graph[current]:
            distance = current_dist + weight

            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(heap, (distance, neighbor))

    return distances


graph = {
    "A": [("B", 4), ("C", 1)],
    "B": [("A", 4), ("D", 1)],
    "C": [("A", 1), ("B", 2), ("D", 5)],
    "D": [("B", 1), ("C", 5)],
}

print(dijkstra(graph, "A"))
# {'A': 0, 'B': 3, 'C': 1, 'D': 4}

Why the heap matters

Without a heap, finding the closest unvisited vertex requires scanning every vertex — O(V) per step, O(V²) total. With a min-heap, the closest vertex is always at the top — O(log V) per extraction.

# without heap — O(V²) total
def find_closest_unvisited(distances, visited):
    closest = None
    min_dist = float("inf")
    for vertex, dist in distances.items():
        if vertex not in visited and dist < min_dist:
            min_dist = dist
            closest = vertex
    return closest

# with heap — O(log V) per extraction
current_dist, current = heapq.heappop(heap)

This is the same min-heap covered in the trees section — heapq always gives instant access to the smallest value. Dijkstra's algorithm is essentially BFS where the "queue" is replaced by a priority queue ordered by accumulated distance instead of discovery order.

Reconstructing the actual path

Track predecessors the same way as BFS shortest path, then walk backward from the target.

import heapq

def dijkstra_with_path(graph, start, target):
    distances = {vertex: float("inf") for vertex in graph}
    distances[start] = 0
    predecessor = {vertex: None for vertex in graph}

    heap = [(0, start)]
    visited = set()

    while heap:
        current_dist, current = heapq.heappop(heap)

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

        if current == target:
            break

        for neighbor, weight in graph[current]:
            distance = current_dist + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                predecessor[neighbor] = current
                heapq.heappush(heap, (distance, neighbor))

    # reconstruct path
    path = []
    vertex = target
    while vertex is not None:
        path.append(vertex)
        vertex = predecessor[vertex]
    path.reverse()

    return path, distances[target]


path, dist = dijkstra_with_path(graph, "A", "D")
print(f"Path: {' → '.join(path)}, Distance: {dist}")
# Path: A → C → B → D, Distance: 4

The limitation — negative weights

Dijkstra's algorithm assumes all weights are non-negative. If a graph has negative edge weights, Dijkstra can produce incorrect results, because it permanently commits to a vertex's shortest distance once visited — but a negative edge discovered later could actually offer a shorter path.

Algorithm	Handles negative weights	Time complexity
Dijkstra	No	O((V + E) log V)
Bellman-Ford	Yes	O(V × E)
Floyd-Warshall (all pairs)	Yes	O(V³)

For graphs with negative weights, use Bellman-Ford instead. It is slower but correctly handles negative edges, and can even detect negative cycles (a cycle whose total weight is negative, which would make "shortest path" undefined).

BFS vs Dijkstra — side by side

	BFS	Dijkstra
Graph type	Unweighted	Weighted (non-negative)
Data structure	Queue (FIFO)	Min-heap (priority queue)
Guarantees	Fewest edges	Lowest total weight
Time	O(V + E)	O((V + E) log V)

Real use cases

GPS navigation — roads as weighted edges (distance or time), finding the fastest route.

Network routing protocols — finding the lowest-latency path between routers.

Flight booking — cities as vertices, flights as weighted edges (price or duration).

Game pathfinding — NPCs navigating a map with varying terrain costs.

Complexity

	Time	Space
Dijkstra (with min-heap)	O((V + E) log V)	O(V)
Dijkstra (without heap)	O(V²)	O(V)

Shortest Path

On this page