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!
Problem Definition:
Consider the task to find the shortest distance between Point A and Point E in the below graph
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 |
- 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).
The Excel solver setup would look like this.
The Solution would be as below
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)
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)
Well-documented!
Thanks for the feedback. Appreciate you taking time and dropping a note
😃