Shortest Path

1. 1.Shortest Path in Binary Matrix
   Equal-cost 8-direction grid → BFSmedium
2. 2.Word Ladder
   Implicit unweighted graph → BFS / bidirectional BFShard
3. 3.Open the Lock
   State graph; every wheel turn costs 1 → BFSmedium
4. 4.Network Delay Time
   Non-negative weighted graph → Dijkstramedium
5. 5.Cheapest Flights Within K Stops
   Cost plus stops-used statemedium
6. 6.Path With Minimum Effort
   Minimize maximum edge cost → modified Dijkstramedium
7. 7.Swim in Rising Water
   Minimax path → Dijkstra or binary search + reachabilityhard
8. 8.Minimum Cost to Make at Least One Valid Path in a Grid
   Edges cost only 0 or 1 → dequehard
9. 9.Minimum Obstacle Removal to Reach Corner
   Entering a cell costs 0 or 1 → 0-1 BFShard
10. 10.Shortest Path with Alternating Colors
    State is (node, last edge color)medium
11. 11.Bus Routes
    Model stops and routes, then BFS by buses takenhard
12. 12.Minimum Genetic Mutation
    Implicit equal-cost mutation graph → BFSmedium
13. 13.Snakes and Ladders
    Board squares form an unweighted state graphmedium
14. 14.Rotting Oranges
    All rotten cells start together → multi-source BFSmedium
15. 15.01 Matrix
    Start from every zero → multi-source BFSmedium
16. 16.Bellman-Ford Shortest Path
    Relax all edges V − 1 times; detect negative cyclesmedium
17. 17.Floyd-Warshall All-Pairs Shortest Path
    Try every node as an intermediate pointmedium
18. 18.Shortest Path in DAG
    Topological order + relaxation → O(V + E)medium
19. 19.Dijkstra Shortest Path
    Min heap always expands the cheapest known statemedium
20. 20.0-1 BFS
    Weight 0 to deque front; weight 1 to backmedium

1. 21.Minimum Knight Moves
   Equal-cost moves on an infinite board → BFSmedium
2. 22.Maze Shortest Path
   Grid cells are nodes; valid moves are edgesmedium
3. 23.Minimum Cost Path in Grid
   Weighted cells → Dijkstramedium
4. 24.Find the City With Smallest Number of Neighbors
   Many pair queries → Floyd-Warshall or repeated Dijkstramedium
5. 25.Reachable Nodes in Subdivided Graph
   Dijkstra distances plus remaining moveshard
6. 26.Number of Ways to Arrive at Destination
   Dijkstra with distance and ways arraysmedium
7. 27.Second Minimum Time to Reach Destination
   Track two best arrival times per nodehard
8. 28.Shortest Path Visiting All Nodes
   Bitmask BFS state: (node, visitedMask)hard
9. 29.Minimum Weighted Subgraph With Required Paths
   Combine forward and reverse Dijkstra distanceshard
10. 30.A* Search — Practical Concept
    Dijkstra guided by an admissible heuristichard

1. Every edge has the same cost?BFS
2. Weights are only 0 or 1?0-1 BFS
3. Weights vary but are non-negative?Dijkstra
4. Negative edges may exist?Bellman-Ford
5. Need distances between every pair?Floyd-Warshall
6. Graph is a DAG?Topological order + relaxation

Main decision rule

Equal cost       → BFS
Only 0 / 1       → 0-1 BFS
Non-negative     → Dijkstra
Negative edges   → Bellman-Ford
All pairs        → Floyd-Warshall
DAG              → Topological order + relaxation

func shortestPathBFS(graph [][]int, start int) []int {
    dist := make([]int, len(graph))
    for i := range dist { dist[i] = -1 }
    dist[start] = 0
    queue := []int{start}
    head := 0

    for head < len(queue) {
        node := queue[head]
        head++
        for _, next := range graph[node] {
            if dist[next] != -1 { continue }
            dist[next] = dist[node] + 1
            queue = append(queue, next)
        }
    }
    return dist
}

A ──10──→ B
A ──2──→ C ──3──→ B

Direct:   1 edge,  cost 10
Via C:    2 edges, cost 5 ✓

candidate = dist[u] + weight

if candidate < dist[v] {
    dist[v] = candidate
    parent[v] = u
}

Algorithm Guide

Equal cost → Queue waves
0 / 1 cost → Deque front or back
Varying non-negative cost → Min heap
Negative edge → Repeated relaxation
All pairs → Distance matrix
DAG → Topological order

State, Grids & Path Reconstruction

Cell        → node
Valid move  → edge
Move cost   → edge weight

Equal move cost → BFS
0 / 1 cost      → 0-1 BFS
Varying cost    → Dijkstra

When a distance improves:
parent[next] = current

At target:
target → parent → ... → start
reverse to get start → ... → target

Complexity Cheat Sheet

BFS                 O(V + E)
0-1 BFS             O(V + E)
Dijkstra + heap     O((V + E) log V)
Bellman-Ford        O(VE)
Floyd-Warshall      O(V³)
DAG shortest path   O(V + E)

Common Interview Mistakes

• • Using BFS when edge costs differ — BFS minimizes edge count, not arbitrary total weight.
• • Using normal Dijkstra when negative edges are possible.
• • Marking a Dijkstra node visited like BFS before its best distance is finalized; stale heap entries should be skipped instead.
• • Forgetting the relaxation check before updating a distance.
• • Tracking only the node when stops, colors, keys, or remaining resources change future choices.
• • Confusing a source-to-target shortest route with a minimum spanning tree.
• • Returning only the distance when the interviewer asks for the actual route.

Interview Rules

Shortest Path      → Minimum total cost
Equal weights      → BFS
0 / 1 weights      → 0-1 BFS
Non-negative       → Dijkstra
Negative edges     → Bellman-Ford
All pairs          → Floyd-Warshall
DAG                → Topological + relaxation
Better route       → Relax the edge
Actual route       → Store parent
Extra constraint   → Add it to the state
Shortest path      ≠ Minimum spanning tree

💡 Golden Rule: Before choosing a shortest-path algorithm, inspect the edge costs first; the weight rules decide the algorithm.

Model first: state + edges + weight
Equal move cost: BFS
Different non-negative cost: Dijkstra
Negative edge: Bellman-Ford
All pairs: Floyd-Warshall
0/1 cost: 0-1 BFS
Need route: parent map
Extra constraint: extra state