Shortest Path Algorithm
Shortest Path Algorithm
Imagine youโre standing in a new city with several streets connecting different places.
You want to reach your hotel as fast as possible.
Some streets are short, some are long, and some twist around.
A Graph works just like this mini-map:
- Nodes (or vertices) = places
- Edges = the roads between places
- Weights = distance, time, or cost of traveling through a road
Now the big question is:
How do we find the quickest route from one node to another?
Thatโs exactly what the Shortest Path Algorithm is designed for.
๐บ๏ธ A Simple Graph to Imagine
Here is a small weighted graph.
The numbers represent distances.
(4)
A -------- B
| \ \
(2) (5) (1)
| \ \
C -----(3)---- D- You can go from A to B using a road of length 4.
- You can go from A to C using a road of length 2.
- And so on.
Now suppose you want to go from A to D, but you want the cheapest or shortest route.
๐ฏ What Does a Shortest Path Algorithm Do?
A shortest path algorithm gently explores all possible routes and chooses the one with the lowest total distance.
Think of it like a careful traveler who:
- Checks all the nearby roads first.
- Always picks the smallest distance so far.
- Slowly expands to explore more paths.
- Keeps updating routes whenever a shorter one appears.
Itโs not guessing โ itโs building the best path step by step.
๐ฑ The Most Popular Shortest Path Algorithm: Dijkstraโs Algorithm
There are many algorithms, but if you’re learning Data Structures, youโll usually meet this one first.
Dijkstraโs Algorithm works when:
- All edge weights are positive
- You want the shortest path from one source node to all other nodes
Itโs famous because itโs simple, fast, and used almost everywhere โ
from Google Maps to packet routing in computer networks.
๐ถโโ๏ธ๐ญ Dijkstraโs Algorithm Explained Like a Story
Letโs pretend you start at A and want to find the shortest path to every place.
Here’s how Dijkstra would think:
1. Start at A with distance 0
You are already at A, so it costs nothing to stay there.
2. Look at all neighbors of A
- A โ B = 4
- A โ C = 2
- A โ D (directly) = 5
So your initial table looks like this:
| Node | Distance from A |
|---|---|
| A | 0 |
| B | 4 |
| C | 2 |
| D | 5 |
3. Pick the nearest unvisited node
C has distance 2, the smallest.
So we go to C next.
4. From C, update its neighbors
- C โ D = 2 + 3 = 5
But D is already 5 in our list, so no change.
5. Next nearest unvisited node is B (4)
- B โ D = 4 + 1 = 5
Still equal to our current value.
No improvement.
6. Finally we reach D (5)
No more updates needed.
๐ก Shortest Path from A to D
You can reach D with a total cost of 5.
There are multiple ways:
- A โ D (direct) = 5
- A โ C โ D = 2 + 3 = 5
- A โ B โ D = 4 + 1 = 5
All are equally good.
This sometimes happens โ a graph doesnโt always have โone unique shortest path.โ
๐ง A Real-Life Way to Remember It
Think of Dijkstraโs Algorithm like water filling a valley:
- It starts at the lowest point (your source).
- It spreads outward smoothly.
- It always flows to the next closest point.
- It reaches far-away points only after filling the closer ones.
This makes the idea more natural and easy to recall.
๐ Where Are Shortest Path Algorithms Used?
You might be surprised how often we rely on them:
- GPS Navigation: fastest route from home to office
- Internet Routing: finding efficient paths for data packets
- Games: characters choosing the quickest route
- Transport Networks: least-cost shipping routes
- AI and Robotics: movement planning and obstacle avoidance
Basically, anytime a computer needs to move from point A to B wisely, a shortest path algorithm steps in.
About the Author
