Longest paths: Dijkstra 2
1. Theory
One of the most important tasks in the graph theory is the calculation of the longest and shortest path between a starting node I and an end node J.
The Dijkstra Algorithm is an algorithm that allows you to allocate the shortest path in a graph between a starting node i and an end note j by inlcuding other nodes of the graph.
It can also be used to calculate longest paths, if some simple modifications are used.
The calculation of the longest path demands directed arcs in order to proceed a correct solution.
Furthermore loops have to be eliminated, otherwise the solution would be infinite and therefore invalid.
2. Example
3. Explanation of the problem
In this example we want to find the longest path from node A to node G. To avoid the calculation of every possible path, we use the djikstra algorithm.
Although It might be seem easy to recognize the solution by overviewing the problem, but more complex problems with a lot more nodes,
will make it is necessary to have a working algorithm which can provide a precise and easy solution.
4. Detailed Solution
1. Select starting node as base node.
2. Compute path length to all neighbor nodes of the base node, which have not been base node yet. If the path is longer than the longest one caculated up to now,the new path will be stored.
3. Select that node as new base node, with the longest distance to the starting node and repeat step 2.
4. The optimal solution is found when there are no more paths left that haven’t been calculated.
Step 1:
Select start node A as base node and calculate all paths to neighbor nodes. You have the possibiltity to choose B or C as next node. In this case you choose C because it is the longest path from A. So you have a distance A (A-C = 7)
Step 2:
Select the most distant node from a as next base node (C) and repeat step 2 from above. You have not yet reached the goal node (G). You continue with the next Basic node C calculate all distance from node C. You can go from C to E or from C to F. So yyou have the distance C (C-E = 11) and C (C-F = 15).
Step 3:
The next Iteration step is from E to D and from E to F and check where is the longest path. It could be possibile that the graph have a longer way maybe from E to D. So you have to check all possibilities from one node to another node up to reach your goal node. So you have distance from E (E-D = 12, A-C=7 + C-E=4 + E-D=1). E (E-F=14). So you the way A-C-F=15.
Step 4 and 5:
From node F in this case you have only one possibility to reach the goal node G. F (F-G=20).
Step 6:
You have to check the last node from D to G because it could be possible that the distance from D to G is very long to reach the final node G. To reach G over D you have a distance from A-C-E-D-G= 16. You compare the results and decide to go the longest way.
Longest Path
In this problem you have one way to reached the final node G with longest path namly A-C-F-G= 20. It is very important to check all ways from one node to another node to reach your goal node.
Literature
Müller-Merbach, Operations Research 2. Auflage, Verlag: Vahlen 1971, S. 241-247.
Lecture and script (slide 2.4 to 2.9) from Operation Research Prof. Oliver Wendt SS 2013.
Assignment 1 from Operation Research Tutorial for graph theory.
