Introduction

Dijkstra's algorithm involves using a queue. We use to the queue to maintain a list of nodes which we need to process. As with other graph problems the algorithm will involve short circuiting if we encounter a node which we've seen before.

We will have seen a node before under two conditions.

• We haven't processed this before.
• We've processed this before successfully

Sounds confusing right?

1 reason this condition exists is we haven't processed a node when we haven't processed all it's neighbors/children. 2 is when you've traversed this node recursively successfully(including its neighbors/children).

Practice Problems

• 743. Network Delay Time
• 787. Cheapest Flights Within K Stops
• 994. Rotting Oranges
• 332. Reconstruct Itinerary
• 1514. Path with Maximum Probability
• 2492. Minimum Score of a Path Between Two Cities

Conclusion