Dijkstra’s Algorithm is a foundational graph algorithm used to find the shortest path from a single source to all other nodes in a weighted graph. It’s versatile and appears in a wide range of problems, especially those involving weighted graphs or grids. Let’s break it down and explore its application using

https://leetcode.com/problems/shortest-path-to-get-all-keys/ [Hard]
https://leetcode.com/problems/cheapest-flights-within-k-stops/ [Medium]

1. Recognizing Problems That Suit Dijkstra’s Algorithm

Dijkstra’s is typically suited for Weighted Graph Problems where ****you need the shortest or cheapest path, but edge weights vary or Single Source Problems where you start from a source node and calculate the shortest paths to other nodes in a specific order.

<aside> ⚠️

The edge weights must be non-negatives. If we have negative weights, we must take a different approach (like Bellman-Ford Algorithm)

</aside>

Key Examples

In Shortest Path to Get All Keys: is a type of Single Source Problem where we want to find the shortest path from source A while collecting keys in the grid in a specific order.

In Cheapest Flights Within K Stops: is a type of Weighted Graph Problem, which is a cost minimization problem. We want to reduce the cost of a journey within certain constraints.

Traditional BFS vs. Dijkstra’s Algorithm

Since Dijkstra is applicable for problems where we’re looking for the shortest path in a grid, it’s important to learn spot whether a vanilla BFS would be sufficient or if we need to need to use more advanced techniques like Dijkstra. Here are some helpful decision criteria:

Observation	Answer
Edge have weights?	✅ Traditional BFS doesn’t account for weight but Dijkstra does
Is there a priority traversal needed?	✅ Dijkstra is well suited for this via the priority queue usage
Can edges be negative?	❌ Bellman-Ford is a better fit

If we recognize these criteria as relevant then let’s proceed with solving the problem using this algorithm.

2. Steps to Solve a Dijkstra’s Problem

Single Source Problem

We will first start by looking at how we solve a single source problem (such as The Maze) and then we will discuss the differences when tackling a weighted graph problem instead.