What is Dijkstra’s Algorithm?
Understand Dijkstra’s shortest-path algorithm, its greedy priority-queue approach, complexity, and common interview pitfalls.
Expected Interview Answer
Dijkstra’s algorithm finds the shortest path from a single source vertex to every other vertex in a weighted graph with non-negative edge weights, using a greedy strategy backed by a priority queue.
It maintains a running "best known distance" for every vertex, starting at zero for the source and infinity elsewhere. On each step it pulls the unvisited vertex with the smallest known distance from a min-heap, marks it finalized, and relaxes its outgoing edges — updating a neighbor’s distance if going through the current vertex is cheaper. Because weights are never negative, once a vertex is popped its distance can never improve later, which is what makes the greedy choice correct. With a binary heap this runs in O((V + E) log V).
- Guarantees optimal shortest paths on non-negative graphs
- Efficient with a priority queue: O((V+E) log V)
- Basis for routing protocols and mapping software
- Extends naturally to single-source, all-destinations queries
AI Mentor Explanation
Think of a bowling coach ranking net sessions by fatigue cost instead of distance. He keeps a shortlist of players sorted by lowest cumulative fatigue so far, always working on the least-tired player next, and updates teammates’ fatigue scores whenever a shorter path through the current player is found. Once a player’s fatigue score is locked in as the smallest remaining, it never gets revised again, because every extra session only adds more fatigue, never subtracts it.
Step-by-Step Explanation
Step 1
Initialize distances
Set source distance to 0 and every other vertex to infinity; push all into a min-priority-queue.
Step 2
Pop the minimum
Extract the unvisited vertex with the smallest known distance and mark it finalized.
Step 3
Relax neighbors
For each outgoing edge, if dist[u] + weight(u,v) < dist[v], update dist[v] and re-insert into the queue.
Step 4
Repeat until empty
Continue popping and relaxing until the queue is empty; all finalized distances are shortest paths.
What Interviewer Expects
- Correct explanation of why the greedy pop is safe only with non-negative weights
- Priority-queue-based implementation, not brute force
- Time complexity: O((V+E) log V) with a binary heap
- Awareness that negative weights require Bellman-Ford instead
Common Mistakes
- Applying Dijkstra to graphs with negative edge weights
- Forgetting to skip already-finalized vertices popped again from the heap
- Using a plain array scan instead of a heap, degrading to O(V²) unnecessarily
- Confusing single-source shortest path with all-pairs shortest path (Floyd-Warshall)
Best Answer (HR Friendly)
“Dijkstra’s algorithm is how you find the cheapest or fastest route from one starting point to everywhere else in a network, like GPS routing. It always expands the closest unexplored point first and updates its neighbors’ costs, which guarantees the shortest paths as long as costs never go negative.”
Code Example
import heapq
def dijkstra(graph, source):
# graph: {node: [(neighbor, weight), ...]}
dist = {node: float('inf') for node in graph}
dist[source] = 0
visited = set()
heap = [(0, source)]
while heap:
d, u = heapq.heappop(heap)
if u in visited:
continue
visited.add(u)
for v, weight in graph[u]:
new_dist = d + weight
if new_dist < dist[v]:
dist[v] = new_dist
heapq.heappush(heap, (new_dist, v))
return distFollow-up Questions
- Why does Dijkstra fail on graphs with negative edge weights?
- How does A* improve on Dijkstra using a heuristic?
- What is the time complexity difference between array-based and heap-based Dijkstra?
- How would you reconstruct the actual shortest path, not just its distance?
MCQ Practice
1. What is the time complexity of Dijkstra’s algorithm using a binary heap?
Each edge relaxation triggers a heap operation costing log V, giving O((V+E) log V) overall.
2. Dijkstra’s algorithm produces incorrect results when the graph contains:
Negative weights break the greedy assumption that a popped vertex’s distance is final; Bellman-Ford is needed instead.
3. What data structure is essential for an efficient Dijkstra implementation?
A min-priority-queue lets the algorithm repeatedly extract the closest unvisited vertex efficiently.
Flash Cards
What does Dijkstra’s algorithm compute? — Shortest paths from a single source to all other vertices in a non-negative weighted graph.
What structure powers an efficient Dijkstra? — A min-priority-queue (binary or Fibonacci heap) ordered by current known distance.
Why does Dijkstra fail with negative weights? — A finalized vertex’s distance could later be undercut by a path through a negative edge, breaking the greedy guarantee.
What is Dijkstra’s time complexity with a binary heap? — O((V + E) log V), where V is vertices and E is edges.