Dijkstra Algorithm

Introduction

Dijkstra Algorithm is a core Trees & Graphs topic used in coding interviews, production systems, and system design. Learn the idea, the traversal pattern, the dry run, the complexity, and the mistake interviewers expect you to avoid.

Understanding the topic

Dijkstra finds shortest paths with non-negative edge weights using a priority queue.

• Identify the structure first: tree, graph, DAG, heap, trie, or disjoint set.
• State the traversal or invariant before writing code.
• Track visited state, recursion depth, ordering, and edge cases explicitly.

Visual explanation

Keep this mental picture in your head while solving:

A --- B
|     |
C --- D

Step-by-step explanation

1. Define the input structure and the goal.
2. Choose traversal or data structure: DFS, BFS, heap, trie, DSU, DP, or shortest path.
3. Run on a tiny example and write down state changes after every step.
4. Code the invariant cleanly, then test empty, one-node, skewed, disconnected, and cyclic cases.

Informative example

Reference implementation pattern:

PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
dist[source] = 0;
pq.add(new int[] { source, 0 });
while (!pq.isEmpty()) {
    int[] cur = pq.remove();
    int node = cur[0], cost = cur[1];
    if (cost != dist[node]) continue;
    for (Edge e : graph.get(node)) relax(e);
}

Complexity analysis

• Time: O((V + E) log V)
• Space: O(V + E)

Real-world use

In production, Dijkstra Algorithm appears in file systems, dependency graphs, routing engines, search indexes, recommendation graphs, compiler pipelines, fraud detection, and social feeds. The same reasoning you use in interviews becomes reliability work at scale.

Best practices

• Say the complexity before and after coding.
• Draw the graph/tree and dry-run the first three iterations.
• Use iterative traversal when recursion depth may overflow.
• Name states clearly: unvisited, visiting, visited; or parent, rank, distance.

Common mistakes

• Forgetting visited state in graphs and creating infinite loops.
• Confusing tree constraints with graph constraints.
• Returning too early before exploring all branches.
• Ignoring disconnected components.

Pattern recognition guide

• Recognize when Dijkstra Algorithm appears from the wording: hierarchy, nearest, connected, dependency, route, prefix, or ordering.
• Draw a tiny input and label visited state, queue/stack, parent pointers, or distances.
• Choose the simplest correct pattern before optimizing.

Visual walkthrough

Cheat sheet

Dijkstra: non-negative weights, faster with heap
Bellman-Ford: supports negative edges, detects negative cycles
Floyd-Warshall: all-pairs shortest paths, dense/small graphs

Interview tips

• DFS is natural for exhaustively exploring paths, components, recursion, and backtracking.
• BFS is natural for shortest path in unweighted graphs and level-by-level expansion.
• Use a heap when the next best candidate must be selected repeatedly.

Common mistakes

• Marking visited too late in BFS and enqueueing duplicates.
• Forgetting disconnected components.
• Using Dijkstra with negative edges.

Interview Q&A