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

Principles of the travel scheduling problem

Comment:

Underlying principles of the travel scheduling problem?

Follow-up:

Frankly speaking we also do not know the complete picture of this problem. Yet from an intuitive angle, the problem enlarges the complexity of the original shortest path problem in at least two dimensions. Firstly, we need to solve multiple instances of the shortest path problem for any single round-trip tour (e.g., one day in the trip). Secondly, we need to combine these shortest path solutions temporally across different tours so as to obtain the minimum overall cost for the whole trip.

Dijkstra's shortest path, Computation

Comment 1:

How to derive the Dijkstra’s shortest path algorithm’s estimated running time?

Follow-up:

As an approximation, we note that each link needs to be visited at once. In the worst case, we can have on the order of (n x n) links, where n is the number of nodes in the graph. Thus, the estimated running time is approximately (n x n) steps.

Comment 3:

Maybe it is true that if we put in more computing/storage resources, we can solve just about any problem.

Follow-up:

If you attended Tutorial 3, you should have learned that there are really difficult problems, in the sense that you will need unreasonably large amount of storage (e.g., every atom in the universe) and computing power to solve. Furthermore, in Problem 3 of Tutorial 3, you will see that there are problems that are simply unsolvable.

Dijkstra's shortest path problem

Problem:

We learn about the Dijkstra’s shortest path algorithm in class. Try to apply it to the following graph.

What is the shortest path between s and b?

Follow-Up:

Using Dijkstra and starting from s, the shortest path found is s-a-b. Yet we can easily see that the shortest path should be s-a-c-b. Thus, we can see that greedy method does not always work. Here, Dijkstra is defeated by the existence of links with negative costs.

However, as some of you discovered during the tutorial, the correct shortest path can be found by starting the Dijkstra work from the destination, i.e., b. Please try this yourself.

Indeed, in real-life usage (e.g., in software systems such as MapQuest), a bi-directional approach is used, i.e., the Dijkstra work is done concurrently from both the starting point and the destination. Conflicts are resolved on the way to construct the final shortest path.

Further Inquiry:

Consider that the link costs are multiplied together (e.g., when the links are associated with probabilities) in a path, would Dijkstra still work?