Dijkstra's Algorithm

1. 1.Network Delay Time
   Standard adjacency-list Dijkstra from sourcemedium
2. 2.Path With Minimum Effort
   Distance is minimum possible maximum edge effortmedium
3. 3.Swim in Rising Water
   Minimize the maximum elevation on the pathhard
4. 4.Cheapest Flights Within K Stops
   State must include stops usedmedium
5. 5.Number of Ways to Arrive at Destination
   Track distance and number of equal shortest pathsmedium
6. 6.Minimum Cost to Reach Destination
   Heap ordered by accumulated costmedium
7. 7.Minimum Cost Path in a Weighted Grid
   Cells are nodes; moves carry costmedium
8. 8.Reachable Nodes in Subdivided Graph
   Distances determine remaining moves on each edgehard
9. 9.Path With Maximum Probability
   Use a max heap and multiply probabilitiesmedium
10. 10.Minimum Cost to Make at Least One Valid Path in a Grid
    0/1 weights; compare with 0-1 BFShard
11. 11.Minimum Obstacle Removal to Reach Corner
    Entering an obstacle adds cost 1hard
12. 12.Find the City With Smallest Number of Neighbors
    Run from each source or use Floyd-Warshallmedium
13. 13.Minimum Weighted Subgraph With Required Paths
    Combine forward and reverse Dijkstra distanceshard
14. 14.Second Minimum Time to Reach Destination
    Keep two best arrival timeshard
15. 15.Dijkstra Shortest Path with Path Reconstruction
    Store parent when distance improvesmedium

1. 16.Shortest Path in Weighted Undirected Graph
   Add both directions to adjacency listmedium
2. 17.Shortest Path in Weighted Directed Graph
   Respect edge directionmedium
3. 18.Multi-Source Dijkstra
   Push every source with distance 0medium
4. 19.Dijkstra with Extra State
   Heap contains cost plus complete statehard
5. 20.Dijkstra on Grid
   Encode cells or keep row and column in statemedium
6. 21.Dijkstra with Time / Constraints
   Time or remaining resource changes the statehard
7. 22.A* Search — Practical Extension
   Dijkstra guided by an admissible heuristichard

How to Think

1. Weighted shortest path and all weights non-negative?Dijkstra
2. Main data structure?Min Heap / Priority Queue
3. What does the heap store?(distance, node)
4. What operation repeats?Relax outgoing edges

Take cheapest node
↓
Skip it if the heap entry is stale
↓
Relax neighbors
↓
Push every improvement
↓
Repeat

func dijkstra(n int, graph [][]Edge, start int) []int {
    dist := make([]int, n)
    for i := range dist { dist[i] = INF }
    dist[start] = 0
    pq := MinHeap{{dist: 0, node: start}}

    for pq.Len() > 0 {
        cur := heap.Pop(&pq).(State)
        if cur.dist != dist[cur.node] { continue } // stale
        for _, edge := range graph[cur.node] {
            nextDist := cur.dist + edge.weight
            if nextDist < dist[edge.to] {
                dist[edge.to] = nextDist
                heap.Push(&pq, State{nextDist, edge.to})
            }
        }
    }
    return dist
}

• • Dijkstra is correct only when weights are non-negative.
• • Early exit is safe when the target is popped with its current best distance.
• • Do not mark visited when a node is merely discovered.

Variants & Path Reconstruction

On improvement:
parent[next] = node

Trace target → parent → start
Then reverse the sequence.

better: ways[next] = ways[node]
equal:  ways[next] += ways[node]

Heap top        → cheapest known distance
Stale pop       → skip
Better neighbor → update + push
Target popped   → safe early exit
Negative edge   → invalid algorithm

Complexity

Adjacency list + binary heap
Time:  O((V + E) log V)
Space: O(V + E)

Dense matrix implementation
Time:  O(V²)

Heap operations add the logarithmic factor; use 64-bit distances when path sums can exceed int range.

Common Interview Mistakes

• • Using Dijkstra with a negative edge
• • Using a FIFO queue instead of a min heap
• • Marking visited like BFS
• • Forgetting to skip stale heap entries
• • Reversing the heap order
• • Adding only one direction for an undirected edge
• • Overflowing distance sums or ignoring unreachable nodes
• • Tracking node only when the real state has extra constraints

Interview Rules

Non-negative weights → Dijkstra
Heap               → (distance, node)
Pop                 → cheapest known state
Stale entry         → skip
Better route        → relax + push
Actual route        → parent array
Extra constraint    → extra state
Negative edge       → Bellman-Ford

Dijkstra    → non-negative weighted graph
Priority    → total distance so far
Relaxation  → newDist < dist[next]
Stale entry → poppedDist != dist[node]
Actual path → parent array
Time        → O((V + E) log V)

💡 Golden Rule: Always expand the currently cheapest valid state, then relax its outgoing edges.