Dijkstra’s Algorithm: Finding the Shortest Path

Imagine you are trying to navigate through a sprawling city during rush hour. You need to get from your apartment (Node A) to your office (Node D). If every road took exactly 10 minutes to traverse, you could simply count the number of intersections (Breadth-First Search). However, in the real world, some roads are highways (fast), while others are congested alleys (slow).

Dijkstra’s Algorithm is the definitive solution for finding the shortest path from a starting node to all other nodes in a weighted graph, where each edge has a specific cost or distance.

1. The Core Intuition: Expanding Like a Wave

Think of Dijkstra’s Algorithm like dropping a stone into a pond, creating a wave that ripples outward. The key difference is that the “water” flows at different speeds depending on the edge weights.

The algorithm maintains a “frontier” of nodes it is currently exploring. Instead of exploring all neighbors strictly by depth (like DFS) or by layers (like BFS), it uses a Priority Queue to always pick the node that is closest to the starting point out of all the nodes on the frontier.

The Two Core Operations:

Explore: Always pop the node with the smallest known distance from the Priority Queue.
Relax: Check all neighbors of the current node U. If the path to neighbor V through U is shorter than the previously known distance to V, update the distance to V and push it onto the Priority Queue.

2. Interactive: Dijkstra Step-by-Step

Let’s visualize this. Click Step to advance the algorithm. Notice how the Priority Queue (PQ) keeps the shortest paths at the front, and we only mark a node as “visited” once we pop it from the PQ.

PQ: [(A, 0)]

Dist: {A:0, B:inf, C:inf, D:inf}

3. Complexity Analysis

Metric	Complexity	Explanation
Time Complexity	$O(E \log V)$	We extract a minimum node from the Priority Queue $V$ times ($O(V \log V)$). We traverse every edge and potentially push to the PQ ($O(E \log V)$). Combined, this is $O((V + E) \log V)$, which simplifies to $O(E \log V)$ for connected graphs.
Space Complexity	$O(V + E)$	Storing the graph as an adjacency list takes $O(V + E)$. The Priority Queue and distance map take $O(V)$ space.

4. Edge Cases & Considerations

Negative Weights: Dijkstra’s Algorithm fails if the graph contains negative weight edges. Once a node is popped from the PQ, Dijkstra assumes we have found the absolute shortest path to it. Negative edges break this assumption. If you have negative weights, use the Bellman-Ford algorithm.
Disconnected Graphs: If a node is unreachable from the starting node, its distance remains Infinity. The algorithm gracefully handles this by naturally terminating when the PQ is empty.
Cycles: Positive weight cycles are handled correctly because the visited set and distance checks prevent infinite loops. We only process a node if we found a strictly shorter path.

5. Implementation: Network Delay Time

Let’s look at a classic application: LeetCode’s Network Delay Time. We want to find the time it takes for a signal sent from node K to reach all N nodes in a network.

Java

public int networkDelayTime(int[][] times, int n, int k) {
  Map<Integer, List<int[]>> graph = new HashMap<>();
  for (int[] t : times) graph.computeIfAbsent(t[0], x -> new ArrayList<>()).add(new int[]{t[1], t[2]});

  PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]); // Min Heap (Node, Dist)
  pq.offer(new int[]{k, 0});

  Map<Integer, Integer> dist = new HashMap<>();

  while (!pq.isEmpty()) {
    int[] curr = pq.poll();
    int u = curr[0], d = curr[1];

    if (dist.containsKey(u)) continue;
    dist.put(u, d);

    if (graph.containsKey(u)) {
      for (int[] edge : graph.get(u)) {
        int v = edge[0], w = edge[1];
        if (!dist.containsKey(v)) {
          pq.offer(new int[]{v, d + w});
        }
      }
    }
  }
  return dist.size() == n ? Collections.max(dist.values()) : -1;
}

import "container/heap"

type Node struct { id, dist int }
type MinHeap []Node
func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i].dist < h[j].dist }
func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x interface{}) { *h = append(*h, x.(Node)) }
func (h *MinHeap) Pop() interface{} {
  old := *h; n := len(old); x := old[n-1]; *h = old[0 : n-1]; return x
}

func networkDelayTime(times [][]int, n int, k int) int {
  graph := make(map[int][][]int)
  for _, t := range times {
    graph[t[0]] = append(graph[t[0]], []int{t[1], t[2]})
  }

  pq := &MinHeap{Node{k, 0}}
  heap.Init(pq)
  dist := make(map[int]int)

  for pq.Len() > 0 {
    curr := heap.Pop(pq).(Node)
    u, d := curr.id, curr.dist

    if _, exists := dist[u]; exists { continue }
    dist[u] = d

    for _, edge := range graph[u] {
      v, w := edge[0], edge[1]
      if _, exists := dist[v]; !exists {
        heap.Push(pq, Node{v, d + w})
      }
    }
  }

  if len(dist) != n { return -1 }
  maxDist := 0
  for _, d := range dist {
    if d > maxDist { maxDist = d }
  }
  return maxDist
}

Dijkstra's Algorithm