Finding the shortest path
Day 106 of 149
👉 Full deep-dive with code examples
The GPS Navigation Analogy
When you ask Google Maps for directions:
- It doesn't try every possible route
- It smartly finds the shortest path
- Considers traffic, distance, time
Dijkstra's Algorithm is like the GPS in your phone!
It finds the shortest path between two points in a network.
The Problem It Solves
Finding a good route in a network:
- Cities connected by roads → Which route is shortest?
- Computer networks → Which path has lowest delay?
- Social networks → Who's the closest connection?
You can't just pick the closest next step—sometimes a longer first step leads to a shorter total path!
How It Works
Imagine you're at a city and want to reach another:
- Start at your location (distance = 0)
- Look at all connected cities (note their distances)
- Pick the closest unvisited city
- Update distances to its neighbors (if shorter than before)
- Repeat until you reach the destination
Think of it like exploring a maze, but expanding from the closest point first.
A Simple Example
City A → B (4 km) → D (7 km)
↓ ↘
(1 km) (2 km)
↓ ↘
C ──────────→ D (4 km)
Shortest A to D:
A → C (1 km) → D (4 km) = 5 km ✓
NOT:
A → B (4 km) → D (2 km) = 6 km
Where It's Used
- Navigation apps (Google Maps, Waze)
- Network routing (internet packets)
- Game AI (finding paths for characters)
- Airline route planning
In One Sentence
Dijkstra's Algorithm finds the shortest path between two points by repeatedly expanding from the nearest unvisited location.
🔗 Enjoying these? Follow for daily ELI5 explanations!
Making complex tech concepts simple, one day at a time.
Top comments (0)