Shortest Path Problem - Real LIfe Applications

Ever had 10 different things to do in one day at 10 different locations and wondered what is the most efficient/less time-consuming way to do all of them? Computer Science has the solution to your problem, and it's name is 'Shortest Path' (also referred to as 'Dijkstra's algorithm' or 'Minimum spanning tree').


What 'Shortest Path' is, is an algorithm that computes which path (option) gets you to your goal (destination) with the least possible weight (cost). "In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized."

So let's assume you have to do 5 things today:

1. Go to lunch with your Advisor (he/she is available any time you tell them)
• location: Dining Hall
• estimated time of completion: 40 minutes
2. Do your homework
• location: Library
• estimated time of completion: 5 hours
3. Go to Dr. Jory's office hours
• location: Jepson
• estimated time of completion: 1 hour
4. Do Laundry
• location: Gateway apartments
• time of completion: 1.5 hours

Assuming you are starting from your room in Gateway and you want to eventually end up in your room again to sleep. Some possible paths you can take are shown below:









1 is where you start off, 2 is the dining hall, 3 is the library, 4 is Jepson, 5 is Gateway laundry room, and 6 is your room where you end up.

Taking into account the time each of these activities takes, and the distance/walking times between each of these locations, and the importance/benefit of getting each done, you would assign a specific value called 'weight' to each edge (line).

Then, for each path that takes you from 1 to 6, you would add up the weight of all the segments you follow, and whichever path ended up having the smallest value would be the most efficient/cost-effective way to go about your day.

Now for a simple task like this you may not necessarily need the help of a computing system to run an algorithm, but if you had to make a more complicated and multivariate decision, this could be very helpful.

References:
 https://en.wikipedia.org/wiki/Shortest_path_problem
 https://en.wikipedia.org/wiki/Minimum_spanning_tree#Classic_algorithms

Image References:
 https://upload.wikimedia.org/wikipedia/commons/thumb/5/5b/6n-graf.svg/500px-6n-graf.svg.png