Skip to interview prep
Apexed

223. Dijkstra and Prim look almost identical. What is the difference?

MediumGraph algorithms

Technical
Show model answer

Both grow a tree from a start vertex using a priority queue and the same relaxation loop. The key differs: Dijkstra prioritizes a vertex by its total distance from the source (dist[u] + w), while Prim prioritizes it by the weight of the single cheapest edge connecting it to the tree (w).

So Dijkstra builds a shortest-path tree from one source (directed or undirected, non-negative weights), and Prim builds a minimum spanning tree of an undirected graph (negative weights are fine). The two trees are generally different, and both cost O((V + E) log V) with a binary heap.

Dijkstra and Prim look almost identical. What is the difference — Data structures & algorithms interview question — Apexed