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.
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 c.
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:
