DEV Community

Cover image for Navigating the Maze: Solving Shortest Path Challenges with Dijkstra's Algorithm
Bala Madhusoodhanan
Bala Madhusoodhanan

Posted on

Navigating the Maze: Solving Shortest Path Challenges with Dijkstra's Algorithm

Intro:
In this blog, we will embark on an exciting journey of navigating mazes, unraveling complex challenges, and finding the shortest path to our destination. At the heart of our adventure lies Dijkstra's Algorithm, a powerful tool that has revolutionized the way we solve shortest path problems.

Dijkstra's Algorithm:
Imagine you have a big city with many streets and you want to find the shortest path to get from your home to your favorite ice cream shop. Dijkstra's algorithm is like a magical map that helps you find the quickest way to reach your destination. First, you start at your home and mark it on the map. Then, you look at all the nearby streets from your home and see how long it takes to walk each one to reach different places. You write down the time for each street on the map. Next, you move to the street that takes the least time to walk, and you mark it as your current location. Then, you repeat the process. Look at all the streets connected to your current location and write down the time it takes to walk each one. Keep doing this until you reach the ice cream shop. Each time you move to a new location, you add up the time it took to get there. Finally, you will have the shortest path from your home to the ice cream shop!

Image description

Problem Definition:
Consider the task to find the shortest distance between Point A and Point E in the below graph

Image description

Method 1: Excel Solver

Setup:

  • The Decision variable are the Nodes that needs to be set active. Its a binary variable (Highlighted in Yellow cells)
  • The objective function is to minimize the total distance between the source point A and End point B.
  • Setting up the Ranges.
Range Name Cell Reference
From A4:A14
To B4:B14
Decision E4:E14

Image description

  • Constraints. The Net Flow (Flow Out - Flow In) of each node should be equal to Supply/Demand. Node A (Source Node)should only have one outgoing arc (Net Flow = 1). Node E (Destination) should only have one ingoing arc (Net Flow = -1). All other nodes should have one outgoing arc and one ingoing arc if the node is on the shortest path (Net Flow = 0) or no flow (Net Flow = 0).

Image description

The Excel solver setup would look like this.

Image description

The Solution would be as below

Image description

Method 2: Python

!pip install Dijkstar
from dijkstar import Graph, find_path
graph = Graph ()
graph.add_edge(1, 2, 7)
graph.add_edge(1, 3, 9)
graph.add_edge(1, 6, 14)
graph.add_edge(2, 4, 15)
graph.add_edge(2, 3, 10)
graph.add_edge(3, 6, 2)
graph.add_edge(3, 2, 10)
graph.add_edge(3, 4, 11)
graph.add_edge(6, 3, 2)
graph.add_edge(6, 5, 9)
graph.add_edge(4, 5, 6)
shortest_path = find_path(graph, 1, 5)
#print(graph)
print(shortest_path)
Enter fullscreen mode Exit fullscreen mode

The Output
Shortest Path Output: PathInfo(nodes=[1, 3, 6, 5], edges=[9, 2, 9], costs=[9, 2, 9], total_cost=20)

Conclusion:
Embrace the magic of Dijkstra's algorithm, and whether you're a spreadsheet enthusiast or a coding aficionado, you now have the knowledge and tools to master the art of finding the shortest paths and navigate your way to success

Reference:
Dijkstar Python Library

Top comments (2)

Collapse
 
respect17 profile image
Kudzai Murimi

Well-documented!

Collapse
 
balagmadhu profile image
Bala Madhusoodhanan

Thanks for the feedback. Appreciate you taking time and dropping a note
😃