Shortest Path in Graphs

BFS for Unweighted Graphs

When every edge has the same cost (unweighted graph), BFS finds the shortest path in O(V + E) because it explores nodes in order of distance from the source — level 0, then level 1, then level 2, etc.

The key insight: the first time BFS encounters a node, it has found the shortest path to that node. This is because BFS processes nodes in FIFO order, guaranteeing that nodes closer to the source are visited before farther ones.

The level-by-level pattern is especially useful for problems like Word Ladder, where we need the shortest transformation sequence. Each word is a node, and edges connect words that differ by one letter.

Dijkstra's Algorithm

Dijkstra's algorithm finds the shortest path in a weighted graph with non-negative edge weights. Instead of a queue, it uses a priority queue (min-heap) to always expand the node with the smallest known distance first.

The algorithm maintains a distance array. It repeatedly extracts the unvisited node with the smallest distance, relaxes its outgoing edges (updates neighbor distances if a shorter path is found), and marks it as visited. This greedy approach works because all edge weights are non-negative.

Dijkstra vs BFS

Both algorithms share the same BFS skeleton: explore neighbors, use a container (queue vs heap), and track visited/distances. The difference is the priority ordering — BFS explores in order of level (edge count), Dijkstra explores in order of accumulated weight.

When to Use

• BFS for shortest path when all edges have the same cost (unweighted graph).
• Dijkstra for shortest path when edges have varying positive weights.
• Word Ladder / transformation problems: BFS because each transformation costs 1 step.
• Network Delay Time / cheapest flights: Dijkstra because edges have latency/cost.
• Do NOT use Dijkstra with negative weights — use Bellman-Ford or SPFA instead.
• Do NOT use Dijkstra when you only need the single source to single target — it's the same complexity.

Problems