Application of different shortest path algorithms in daily life

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. (Shortest path problem - Wikipedia, the free encyclopedia, 2011) In other words, when we have to find a path with minimum cost to go from a place to another place which there are a number of intermediate points in between to travel to with different costs, we are dealing with the shortest path problems. It should be noted that the phrase “shortest path” here does not necessarily mean physically shortest distance, but a path with minimum weight which can be measured in, say, time or  monetary cost.

Actually, the shortest path problems are closely related to our daily life. For example, we all have to travel within the campus when we attend different lectures, such as going from Meng Wah Complex (MW) to Main Building (MB) to attend the next lecture.
 

Graph 1: The map of the University of Hong Kong

In fact, we should wisely choose our path so we can travel with least amount of time in order to arrive on time, especially when the next lesson starts only 5 minutes later. This will be an example of shortest path problem and the weight will be the time cost. Certainly different routes will involve different buildings and pathways, which some are less time-consuming. For instance, we may go via Chong Yuet Ming Amenities Centre (CYA) and K K Leung Building (KK), or we may walk on the University Drive to Haking Wong Building (HW) first and pass through the podium of Kadoorie Biological Sciences Building (KBS) amd reach MB. However, there are many other possible routes and it is quite impossible for us to try out all possible route to find the one with least time needed. Therefore, we need a more effective method to find out such path and we may apply the Dijkstra’s algorithm to solve this problem.

Graph 2: A simplified map of the University of Hong Kong with checkpoint marked

The Dijkstra's algorithm is an algorithm that can find the shortest path for a single source graph. The Dijkstra's algorithm adopts the concept of greedy approach. First, we will have to initialize the temporary “estimated time needed” from the starting point (the source which is MW in this case) of every checkpoint in the University of Hong Kong (the node, e.g. CYA, MW, MB).
 
Obviously, the time needed to go to the starting point from the starting point is 0. However we do not know the time needed to go to other checkpoint from the starting point yet so we may take them as infinity. Then we can choose a checkpoint which take the minimum time to go from the starting point (choose any one if there are more than 1 checkpoint needed same minimum time to go to) and update the neighbouring checkpoints’ “estimated time needed”, i.e. if the time needed to go to next checkpoint(CPnext) via the chosen checkpoint(CPchosen) is less, we will go to CPnext via the CPchosen instead and replace the time needed to go to CPnext by the sum of the time needed to go to the CPchosen from starting point and the time needed to go to CPnext from CPchosen. And we repeat the above process until all checkpoints are considered.
 

 So, we know that the Dijkstra’s algorithm is useful in solving this kind of shortest path problem. Then can we apply the Dijkstra’s algorithm to every situation to solve the shortest path problems? Unfortunately, the answer is no. The Dijkstra’s algorithm will fail to find the path with minimum weight if the graph consist of some negative weight. At first glance, this situation seems impossible to happen as you may wonder since there will never be a path that will reduce the time needed for the journey. Yet, according to Robert Sedgewick, "Negative weights are not merely a mathematical curiosity; [...] [they] arise in a natural way when we reduce other problems to shortest-paths problems".(Sedgewick, 2003) (Bellman–Ford_algorithm - Wikipedia, the free encyclopedia, 2011) Besides, the weight need not to be time only. Consider the same situation that you have to go from a place to another in the University of Hong Kong, but you have to pay if you go through some place (e.g. the Run Run Shaw Podium (RR)) and some other place may pay you back instead (e.g. the Starbucks may be giving out free coffee at the Sun-Yat-Sen Place). For simplicity, we may consider go from MW to MB again. Consider you can make a handsome profit (e.g. +$1000) going only from the Main Library New Wing (LBN) to KK, but going from RR to LBN costs you a lot (e.g. -$300) and assume travelling in other checkpoint costs nothing . Then according to the Dijkstra’s algorithm, you will choose the LBN checkpoint at last since the only incoming check point is from RR to LBN which make lower the priority of LBN. And even if you update the neighboring checkpoint of LBN, the cost of MB cannot be changed since other checkpoints are all visited already. So the Dijkstra’s algorithm can not give an optimal solution. And we need another algorithm to deal with this kind of problems and we may apply another method -- the Bellman-Ford Algorithm.

“Bellman-Ford is in its basic structure very similar to Dijkstra's algorithm, but instead of greedily selecting the minimum-weight node not yet processed to relax, it simply relaxes all the edges, and does this |V | − 1 times, where |V | is the number of vertices in the graph” (Bellman–Ford_algorithm - Wikipedia, the free encyclopedia, 2011) This means that we will repeat the updating process of Dijkstra’s algorithm for each checkpoints instead of the neighboring checkpoints only, and repeat this for every checkpoints. This guarantees that every checkpoint is updated every time and promises the optimality of the path even if there are negative weights. Nonetheless, this will result in many repeated procedures (overlapping sub-problems) and we may apply the concept of Dynamic Programming in order to speed up the Bellman-Ford algorithm, i.e. using the previously updated checkpoints’ information to update the next checkpoint.

All in all, the shortest path problems is closely connected to our daily life. This is because many problems can be transformed into shortest path problems, though they may not seems to be shortest path problems at first glance, if we analyze the problems carefully. I think this lead to another observation - we should, in terms of both algorithm and problem solving skills, try to think in multiple-dimension and should not simply limited ourselves into 1 solution only. For example, there are different algorithms to solve the shortest path problems, such as the Dijkstra’s algorithm and Bellmen-ford algorithm covered in this survey and many other not discussed in this survey. However, different algorithms may have their own strengths and drawbacks (e.g. Dijkstra’s algorithm is faster and simpler but cannot deal with graph with negative weights) and we should not be constrained to use 1 only in all situation.

References

1. Shortest path problem - Wikipedia, the free encyclopedia. (2011, 9 23). Retrieved 9 28, 2011, from Wikipedia: http://en.wikipedia.org/wiki/Shortest_path_problem
2. Robert Sedgewick. Algorithms in Java. Third Edition. ISBN 0-201-36121-3. Section 21.7: Negative Edge Weights. http://safari.oreilly.com/0201361213/ch21lev1sec7
3. Bellman–Ford_algorithm - Wikipedia, the free encyclopedia. (2011, 9 23). Retrieved 10 4, 2011, from Wikipedia: http://en.wikipedia.org/wiki/Bellman–Ford_algorithm