Introduction to Shortest Path Variants

You know Dijkstra. You know BFS. But the interview problem has a twist: you can remove $k$ walls, or edges cost $0$ or $1$, or you need the shortest path that visits specific nodes in order.

So, what do you do?

The idea is state expansion. Instead of $dist[node]$, you track $dist[node][extraState]$ where the extra state tracks whatever constraint matters. I'll show you how to recognize these variants and modify your state space.

The algorithm stays the same. We just expand it with additional dimensions.