Hey everyone! I have made a list of 10 variations of Dijkstra's algorithm which may help you while you are preparing for online assessments or interviews.
Quick Recap: Standard Dijkstra
Before jumping into variations, let's remember what standard Dijkstra does:
- Finds shortest path from source to all other nodes
- Uses min-heap to greedily select nearest unprocessed node
- Works only with non-negative edge weights
- Time complexity: O((V + E) log V)
1. Network Delay Time (LC 743)
Pattern: Basic Dijkstra with modified output
Instead of returning distance to a specific node, return the maximum distance among all reachable nodes. If any node is unreachable, return -1.
Why this matters: This tests your understanding of basic Dijkstra and edge case handling. Think of it as a signal broadcast - everyone receives it when the furthest person gets it.
Key insight: After running standard Dijkstra, check max(distances). This is a warm-up problem that appears frequently in OAs.
2. Path with Minimum Effort (LC 1631)
Pattern: Modified cost function (max instead of sum)
The cost of a path is the maximum absolute difference between consecutive cells, not the sum. You want to minimize this maximum difference.
Why this matters: Shows that Dijkstra works for any monotonic cost function, not just addition. The greedy property still holds.
Key insight: When relaxing edges, use new_effort = max(current_effort, abs(height[current] - height[next])) instead of addition. This pattern appears in many grid-based problems where you minimize the "worst" step rather than total cost.
Similar problems: Swim in Rising Water (LC 778)
3. Cheapest Flights Within K Stops (LC 787)
Pattern: Dijkstra with constraints (expanding state space)
Find cheapest flight from source to destination with at most K stops. The constraint on number of stops changes everything.
Why this matters: You cannot use standard visited set optimization. You might visit the same node multiple times with different numbers of stops.
Key insight: State becomes (node, stops_used) instead of just (node). You need to track the best cost for each (node, stops) pair. This is crucial - many candidates fail here because they try to mark nodes as visited.
Pro tip: This pattern appears whenever there are constraints on path properties (max edges, required visits, etc.)
4. Path with Maximum Probability (LC 1514)
Pattern: Maximization instead of minimization
Find path with maximum probability (multiply probabilities along edges) instead of minimum cost.
Why this matters: Tests understanding that Dijkstra is fundamentally about greedy optimization, not just minimization.
Key insight: Use max-heap (negate values in Python), multiply probabilities instead of adding, and update when new_probability > current_probability. The greedy property works for maximization too!
Watch out: Make sure to handle probability comparisons with floating point carefully.
5. Minimum Cost to Make at Least One Valid Path (LC 1368)
Pattern: 0-1 weighted graphs
Grid with arrows. Following arrow = cost 0, changing direction = cost 1. This creates a 0-1 weighted graph.
Why this matters: When all edges have weight 0 or 1, you can optimize Dijkstra using 0-1 BFS with a deque instead of priority queue. Runs in O(V + E) instead of O((V + E) log V).
Key insight: While Dijkstra works fine here, mentioning 0-1 BFS optimization in interviews shows advanced knowledge. The pattern: edges with only two possible weights.
Interview tip: Always look for binary edge weights - it's an optimization opportunity.
6. Swim in Rising Water (LC 778)
Pattern: Minimizing maximum value on path
Find path where the maximum elevation encountered is minimized. Similar to "Path with Minimum Effort" but simpler.
Why this matters: Another example of modifying the cost metric. Instead of summing costs, track the maximum.
Key insight: Use max(current_time, grid[next_cell]) as the cost. Can also be solved with binary search + BFS, but Dijkstra is more intuitive once you understand the pattern.
Common mistake: We often try to use BFS without considering that different paths to same cell can have different maximum heights.
7. Reachable Nodes in Subdivided Graph (LC 882)
Pattern: Dijkstra with additional counting logic
Edges have intermediate nodes. Count how many total nodes (original + intermediate) are reachable within maxMoves.
Why this matters: Dijkstra is used for the distance calculation, but requires additional problem-specific logic afterward.
Key insight:
- Run standard Dijkstra to find distances to original nodes
- For each edge, calculate how many intermediate nodes reachable from both ends
- Use
min(intermediate_count, reachable_from_u + reachable_from_v)to avoid double-counting
8. Minimum Weighted Subgraph With Required Paths (LC 2203)
Pattern: Multiple source Dijkstra + graph reversal
Two sources, one destination. Find minimum cost where paths can share edges.
Why this matters: Shows that running Dijkstra multiple times and combining results can solve complex problems.
Key insight:
- Run Dijkstra from src1 (normal graph)
- Run Dijkstra from src2 (normal graph)
- Run Dijkstra from destination on reversed graph (gets distances TO destination from all nodes)
- For each node i: answer = min(dist1[i] + dist2[i] + dist_to_dest[i])
Catch: Reversing directed graph + Dijkstra = distances from all nodes TO a destination.
Similar pattern: Many multi-source/destination problems use this approach.
9. Minimum Time to Visit Disappearing Nodes (LC 3112)
Pattern: Dijkstra with dynamic constraints
Nodes disappear at specific times. Can only visit if you arrive before disappearance.
Why this matters: Tests handling of time-dependent or dynamic constraints during path exploration.
Key insight: Add validation during edge relaxation: if arrival_time < disappear_time[node] and arrival_time < dist[node]. Must check BOTH conditions.
10. Shortest Path Visiting All Nodes (LC 847)
Pattern: State compression using bitmask
Visit all nodes (can revisit) and return shortest path length. Can start from any node.
Why this matters: Most advanced pattern - combines Dijkstra concepts with bitmask state compression.
Key insight:
- State is (node, visited_bitmask) where bitmask tracks which nodes visited
- Can revisit nodes with different visited sets
- Goal: reach any node where bitmask = (1 << n) - 1 (all bits set)
- Since edges have weight 1, use BFS instead of Dijkstra
This is huge: Bitmask state compression appears in many hard problems (TSP, Hamiltonian paths, etc.)
Final Thoughts
The real skill in interviews isn't memorizing these 10 solutions. It's pattern recognition, understand these patterns and apply these concepts on other problems.Once you train yourself to spot these patterns, new Dijkstra problems become much easier.
Hope this helps with your interview prep! Feel free to ask questions and suggest other variations I might have missed.
Comment down your favourite graph question , where your struggled and learnt something new !!
Good luck! 🚀