Shortest Path Algorithm

Posted on by

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:

  1. Checks all the nearby roads first.
  2. Always picks the smallest distance so far.
  3. Slowly expands to explore more paths.
  4. 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:

NodeDistance from A
A0
B4
C2
D5

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.