Longest paths: Dijkstra 3
Theory
The importance of graph theory involves the calculation of the longest paths in graph. In order to determine the longest execution paths using the standard graph algorithms like the Dijkstra’s Algorithm, one must use the reachability graph to arrive at the answer. The problem with finding the longest path is to determine what the longest path is using a given graph. There are some polynomial time algorithms to determine the longest path in a graph, however the authors are only aware of trees being the only natural and non-trivial graph where LPP can be interpreted in polynomial time. Dijkstra was the one that discovered the algorithm for trees in the year of 1960.
In the narrow sense, in order to reach the desired node i, one must pass through various nodes on the way to reach the goal node j. The longest path is only easy to determine if all the edges are directed and the graph contains no cycles. However, if the graph contains cycles and different passages are allowed by each node and edge, the longest path is infinite.
The longest path is useful when one is allowed to only pass each node once. Suitable for solving small problems are all decision tree methods especially for the dynamic lot size creation. The problem has the similar structure as the Travelling Salesman Problem.
Example
Level the graph in order to find the longest path from node A to node L
Split the graph into n levels [n=1…N]:
1. Set the start node to the first level. Remove all predecessors of the starting node. Thus, this node has no more predecessors.
2. Eliminate all nodes with predecessor count = 0 and the outgoing edges. Thereby the predecessor count of all neighbor nodes is changed.
3. Calculate the predecessor enumerate for all neighbor nodes of the last taken node. Do this by counting the number of incoming edges (without the taken ones). If there are nodes with predecessor count=0, set them into a new level (L = n+1). Keep on with step 2.
Repeat step 2 and 3 until there are not any nodes with predecessor count ≠ 0 left.
Literature
Müller-Merbach, Operations Research, 3. Auflage, durchges. A. (1973), Vahlen
Ryuhei Uehara,Yushi Uno Efficient Algorithms for the Longest Path Problem in Algorithms and Computation, 2005 Springer
Prof. Dr. Wendt, Oliver ; Review course 2012 , Business Information Systems & Operations Research , TU Kaiserslautern
RYUHEI UEHARA,YUSHI UNO, ON COMPUTING LONGEST PATHS IN SMALL GRAPH CLASSES,2007, International Journal of Foundations of Computer Science
