Longest paths: Dijkstra 4
1. Theory
The Dijkstra algorithm, which was invented by the Dutch computer scientist Edsger W. Dijkstra, is an algorithm to solve the shortest path problem. So with it, it is possible to calculate the shortest path from a starting node to a end node. But it is also possible to use this algorithm to calculate the longest path from a starting node to a end node (longest path problem). For this, the algorithm has to be modified a little bit (now you have to choose in every step the node with the longest distance). To use the dijkstra algorithm for this problem there are two conditions. First the graph has to be directed and second it should have no loops. If this conditions are not given there will be a invalid (infinitely) solution.
2. Explanation/Example
Longest path problem:
We want to find the longest possible path from a start node to a goal node, which are both defined before applying the algorithm. In this particular case the start node is defined as A, furthermore the goal node is G.
Let’s start with the step-by-step solution to this special problem:
a) Define any node as start, which is your first base node
b) Analyze every path length to the neighbor nodes of your previous base node, which haven’t already been visited. If there is a longer path than the longest you determined yet, this one will be your new path.
c) The node which is reached with this path(longest path up to now) will be your new base. Now you have to repeat step b.
d) If there are no other paths left, you found the optimal solution(longest way from node A to G).
Now we apply the mentioned steps on this example:
Legend:
red arrows: paths, which are already visited
black arrows: paths, which are not visited yet
Iteration 1:
Like already mentioned above, we choose node A as our start. Based on this, we only have two possibilities: from A to B and from A to C. In fact that we want to get the longest way, we obviously have to choose A-C first(total lenght=6).
Iteration 2:
C is our new base node now. So we have to repeat step b), which is shown in the explanation. Again we analyze every path that displays away from node C: lenght of C-E=3(->A-C-E=11) and C-F=7(->A-C-F=13). Furthermore we have to check, if the way from C to F over E isn't longer than the direct way C-F: 3+2<7 ->A-C-F longer than A-C-E-F --> therefore our new path is A-C-F (total lenght=13)
Iteration 3:
F is our next base node. There is only one path that shows away from F, which leads to our previously defined goal node G: lenght of F-G=4 --> new path: A-C-F-G(total lenght=17)-->temporarily longest path
Iteration 4:
After we found a first temporarily longest path, we have to take all other ways, which haven't been visited yet, into consideration to check if there is no longer path than A-C-F-G. A-C-E-D-G is shorter than A-C-F-G, so we can reject this way.
Iteration 5:
Checking th way to G over node D on direct way: A-B-D-G is shorter than A-C-F-G, so we reject it.
Iteration 6:
Checking the indirect way to D: B-E-D=5-1=6<B-D=7 -> shorter than A-C-F-G derived from iteration 5
-->all paths were taken into consideration
In fact that we calculated all ways and didn't find a longer way after iteration 3, our final solution is path A-C-F-G!
-->longest path with a total distance of 17
Sources
1)Script from Operation Research Prof. Oliver Wendt SS 2013.
2)Wikipedia: Dijkstra ([1])
Longest path problem ([2])
3)Wolfgang Domschke • Andreas Drexl: Einführung in Operations Research
