Dijkstra vs Prim

This is a very common interview question.

---

Dijkstra

Find shortest paths from a source.

Example:

A --1-- B
|      /
4     2
|   /
C

From A:

dist(A)=0
dist(B)=1
dist(C)=3   (A->B->C)

We care about:

Shortest distance from source

---

Prim

Build a tree connecting all nodes with minimum total cost.

Same graph:

A --1-- B
|      /
4     2
|   /
C

MST:

A --1-- B
B --2-- C
 
Total cost = 3

We care about:

Minimum total cost to connect everything

Not shortest paths.

---

Heap Contents

Dijkstra

[distanceFromSource, node]

Example:

[5, "C"]

means:

Shortest known distance from source to C is 5

---

Prim

[edgeWeight, node]

Example:

[5, "C"]

means:

Cheapest edge that can add C to the MST costs 5

Notice the subtle difference.

---

Easy Interview Memory Trick

Dijkstra

"How far is this node from the source?"

Prim

"What's the cheapest way to connect a new node?"

---

Complexity

With adjacency list + min heap:

Dijkstra: O(E log V)
Prim:     O(E log V)

---

Microsoft Interview One-Liner

Dijkstra finds shortest paths from one source.
Prim finds the cheapest tree connecting all nodes.