Dijkstra's Algorithm

Given a weighted undirected graph with V vertices (0 .. V-1), edges edges[i] = [u, v, w] with non-negative weight w, return the shortest distance from source vertex 0 to every vertex, or -1 if unreachable.

Hints

· Stuck? Reveal one nudge at a time.

Repeatedly settle the closest unsettled vertex — its distance is final with non-negative weights.

Relax the settled vertex's edges to improve neighbours' distances.

Use a min-heap to fetch the closest vertex in O(log V).

Common doubts

The greedy 'closest is final' step fails with negative edges, since a later negative edge could shorten an already-settled path.

A vertex can be pushed several times as its distance improves; when popped with an outdated (larger) distance, skip it.

The O(V²) scan is fine for dense graphs; the heap's O((V+E) log V) wins when edges are sparse.

Interview follow-ups

· What an interviewer asks next.

Store a parent whenever you relax an improving edge, then backtrack from each vertex.

Use Bellman-Ford, which handles negatives (and detects negative cycles) at O(V·E).

Fun facts

Dijkstra devised this in 1956 — reportedly in about twenty minutes at a café.
With a Fibonacci heap it improves to O(E + V log V).

Asked at

AmazonGoogleMicrosoft

Frequently Sometimes Occasionally

Example 1

Input: V = 4, edges = [[0,1,1],[0,2,4],[1,2,1],[2,3,1]]
Output: [0, 1, 2, 3]
0→1→2→3 gives 0,1,2,3 (0→2 direct of 4 is beaten by 0→1→2 = 2).

Example 2

Input: V = 4, edges = [[0,1,2],[2,3,3]]
Output: [0, 2, -1, -1]
Vertices 2 and 3 are unreachable from 0.

Constraints

- 1 <= V <= 10^5 - 0 <= edges.length <= 10^5 - 1 <= w <= 10^9 - no negative weights

Dijkstra's algorithm finds single-source shortest paths when all weights are non-negative. It's greedy: keep tentative distances, and repeatedly settle the closest unsettled vertex — its distance can no longer improve, because every remaining path leaves through an equal-or-farther vertex. Relax the settled vertex's edges (dist[v] = min(dist[v], dist[u] + w)) and continue.

The difference between the two implementations is how you find the closest unsettled vertex:

Linear scan — check all V vertices each round: O(V²). Fine for dense graphs.
Min-heap — pop the closest in O(log V); push improved distances (ignoring stale entries): O((V+E) log V). Best for sparse graphs.

Prerequisites

Before you start

· Concepts used directly in the solution.

Greedy settling. non-negative weights make the closest vertex final.

Edge relaxation. dist[v] = min(dist[v], dist[u] + w).

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Setup

“Can weights be negative?”

No — Dijkstra requires non-negative weights.

“Source and unreachable?”

Source is 0; unreachable vertices are -1.

The ideal opening — say it like this

I settle the closest unsettled vertex and relax its edges, using a min-heap to fetch the closest in log time.

Non-negative weights guarantee a settled vertex's distance is final.

Understand the problem

Worked example — V = 4, edges [[0,1,1],[0,2,4],[1,2,1],[2,3,1]]

settle 0 (0); relax -> dist[1]=1, dist[2]=4
settle 1 (1); relax -> dist[2]=min(4,2)=2
settle 2 (2); relax -> dist[3]=3
dist = [0, 1, 2, 3]

Key observations

1Aha

Settle the closest first

Its distance is final under non-negative weights.

2Aha

Min-heap fetches the closest

O(log V) per operation vs O(V) scan.

3Aha

Skip stale heap entries

A popped distance greater than the recorded one is outdated.

Brute force vs optimal

	Linear scan	Min-heap
Find closest	scan all V vertices	pop the heap
Time	O(V²)	O((V+E) log V)
Best for	dense graphs	sparse graphs

Both compute the same distances; the heap wins on sparse graphs. Full code is in the Approaches selector below.

Summary

Key takeaway

Dijkstra settles the closest unsettled vertex and relaxes its edges. A min-heap fetches the closest in O(log V), giving O((V+E) log V). Requires non-negative weights.

dist[0]=0; heap=[(0,0)]
pop (d,u); if stale skip; relax edges; push improved