Dijkstra's Algorithm in Python

Ever wondered how Google Maps finds the absolute fastest way home with traffic, speed limits, and distance? Welcome to Dijkstra's Algorithm! 🚗💨

What is it?

While a basic Breadth-First Search (BFS) just counts the number of "hops" to get somewhere, it assumes every road takes the exact same amount of time.

But in the real world, some roads are highways and some are bumpy dirt roads! We call these "Weights" (like distance, time, or tolls). Dijkstra's Algorithm finds the shortest path on these weighted graphs.

How It Works (The Roadtrip Strategy)

Imagine you are at home (Distance = 0) and everywhere else is infinitely far away (∞) until you discover a route there.

1. You keep a Priority Queue (like a super-smart to-do list) of places to explore next. It always pushes the closest known place right to the top!

2. You "drive" to the closest place on your list.

3. You look at all the neighboring towns from there. If the trip from (Home → Current Place → Neighbor) is shorter than the route you previously knew, you update your map and add the neighbor to your to-do list!

4. Repeat until you reach your destination.

Important: Dijkstra only works if there are no "negative weights" (like a magical road that somehow gives you back gas and time!). For that, you'd need the Bellman-Ford algorithm.

Super Fast & Efficient

Using Python's built-in heapq module (a min-heap that keeps the smallest number at the top), we can do this incredibly fast:

Real-World Magic 🌍