Dijkstra shortest paths

Dijkstra finds shortest paths from a source when all edge weights are non-negative. It repeatedly takes the unsettled node with the smallest known distance and relaxes outgoing edges. A priority queue keeps selection efficient on sparse graphs.

Trade-off: compare time, memory, and implementation complexity before committing to a structure or pattern.

On interviews: Interviewers check whether you reject negative weights, store distances separately from visited state, and ignore stale queue entries safely.

Common pitfalls: Plain BFS is correct only for unweighted or equal-weight graphs. Marking a node visited too early can freeze a non-final distance. Negative edges require another algorithm.

Checklist:

• Require non-negative weights.
• Use a min-priority queue.
• Relax edges.
• Skip stale distances.