Dijkstra's Algorithm

Tags

Dijkstra's Algorithm

Category

Famous Algorithms

Difficulty

Hard

Problem Statement

Given a weighted directed graph with non-negative edge weights and a source vertex, find the shortest path distances from the source to all other vertices. Return an array where the value at each index represents the shortest distance from the source to that vertex. If a vertex is unreachable, its distance should be -1 (or infinity).

Intuition

Dijkstra's algorithm is a greedy algorithm. It maintains a set of vertices whose shortest distances are finalized and repeatedly selects the unvisited vertex with the smallest tentative distance. The greedy choice is correct because all edge weights are non-negative: once a vertex has the smallest tentative distance among all unvisited vertices, no future path through other unvisited vertices could be shorter.

Using a min-heap (priority queue) allows efficient extraction of the vertex with the minimum tentative distance.

Approach

  1. Initialize a distances array with infinity for all vertices except the source (distance 0).
  2. Insert the source into a min-heap with distance 0.
  3. While the heap is not empty: a. Extract the vertex u with the minimum distance. b. If the extracted distance is greater than the recorded distance, skip (stale entry). c. For each neighbor v of u:
    • Compute newDist = distances[u] + weight(u, v).
    • If newDist < distances[v], update distances[v] = newDist and insert (newDist, v) into the heap.
  4. Replace any remaining infinity values with -1 (unreachable).
  5. Return the distances array.

Pseudocode

function dijkstra(graph, source):
    n = number of vertices
    distances = array of n, all INFINITY
    distances[source] = 0
    minHeap = new MinHeap()
    minHeap.insert((0, source))

    while minHeap is not empty:
        (dist, u) = minHeap.extractMin()
        if dist > distances[u]:
            continue  // stale entry
        for (v, weight) in graph[u]:
            newDist = dist + weight
            if newDist < distances[v]:
                distances[v] = newDist
                minHeap.insert((newDist, v))

    for i from 0 to n - 1:
        if distances[i] == INFINITY:
            distances[i] = -1

    return distances

Time & Space Complexity

  • Time: O((V + E) log V) with a binary min-heap, where V is the number of vertices and E is the number of edges. Each vertex is extracted once, and each edge triggers at most one heap insertion.
  • Space: O(V + E) for the graph representation and O(V) for the distances array and heap.

With a Fibonacci heap, the time complexity improves to O(V log V + E), but this is rarely used in practice.

Key Insights

  • Dijkstra's algorithm requires non-negative edge weights. With negative weights, use Bellman-Ford instead.
  • The "lazy deletion" approach (inserting duplicates into the heap and skipping stale entries) is simpler than implementing decrease-key and works well in practice.
  • Dijkstra's is essentially BFS with weighted edges: BFS works when all weights are 1, Dijkstra generalizes to arbitrary non-negative weights.
  • The algorithm finds shortest paths in a single-source, all-destinations manner. For all-pairs shortest paths, run Dijkstra from each vertex or use Floyd-Warshall.
  • For unweighted graphs, simple BFS is more efficient than Dijkstra's.

System Design Application

Dijkstra's algorithm depends on the min-heap data structure for efficient priority extraction. The min-heap provides O(log V) extract-min and O(log V) insert operations that make the algorithm achieve O((V + E) log V) time complexity. See min-heap-construction for the data structure implementation details.

Edge Cases

  • Source vertex has no outgoing edges: all other vertices are unreachable.
  • Graph with a single vertex: distance to self is 0.
  • Disconnected graph: unreachable vertices get distance -1 (or infinity).
  • Graph with self-loops: they are ignored since they cannot reduce any distance (assuming non-negative weights).
  • Multiple edges between the same pair of vertices: the algorithm naturally handles this by considering all of them.
  • All edge weights are 0: the algorithm still works, finding all reachable vertices with distance 0.

Linked mentions