Longest paths: Dijkstra 1

Theory

In contrast to the problem of finding the shortest paths in graphs, the problem concerning the longest paths cannot be solved by using the conventional Dijkstra-Algorithmus. The reason for that is that the longest paths problem cannot be solved in polynomial time. The algorithms, which are able to do so, are considered to be fast solving algorithms. The regular Dijkstra-algorithm is one of them. However, the longest path problem is a problem with a higher NP-hardness (Non-deterministic Polynomial-time hardnes), which means that it cannot be solved while satisfying the time restriction of polynomial time. As a result, the NP-hardness of the longest path problem is higher than the NP-hardness of a shortest path problem, which means that another algorithm is needed.

---

In the following two different possible algorithms shall be introduced, whereby the longest path problem can be solved.

One of them is the Bellman-Ford algorithm, a modification of the Dijkstra algorithm, which was named after its inventors Richard Bellman und Lester Ford. Originally, this algorithm was invented to solve shortest path problems as well, but in order to find the longest paths, it is possible to turn around the signs of the edges in the regarded graph. As the Dijkstra Algorithm doesn’t allow negative weights on the edges, the Bellman Ford algorithm does. The most important premise for using this algorithm is that there is no cycle in the graph, in which the edges have a negative sum. In this case an endless loop would be generated and no longest path will be found.

The second possibility to solve a longest path problem is the algorithm for the calculation of the critical path in a numbered network plan. In the following this possibility will be illustrated with the help of an example.

Example

To visualize the problem, the construction of a building shall serve as an example. The different stages in the construction (planning, building the ground plan, building the 1st floor, etc.) shall be depicted in the network plan as different nodes. To proceed to an arbitrary stage, first, the previous stage has to be finished. In the illustrative example, the ground floor has to be finished, before the construction of the 1st floor can start. The algorithm for the calculation of the critical path computes which certain path in the network is the critical one. Explicitly, the algorithm depicts the path, in which there is not allowed any delay, if the finalization of the whole building shall not be delayed.

Process with detailled solution

Notations

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \lambda_i^*

depicts the longest path found up to this point concerning the node i, the star ‚…*‘ means that this depicted value can be changed all during the algorithm.

$M_{j}$ stands for the predecessor which has to be travelled for finding the longest path. There can be more than only one predecessor.

$t_{x,z}$ stands for the distance between two edges $x$ and $z$ regarded in the specific step.

$S_{i}$ depicts the regarded edge.

Process

We set $\lambda _{0}=0$ (edge $S_{0}$) because this is the starting node, until this point, there is no way travelled at all. The ending node is $S_{7}$ . Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \lambda_0^*=0

The algorithm takes every single node and compares every possible way from the starting-node to the regarded node. The longest way to reach it will be chosen as the best one.

First, node $S_{1}$ is regarded. The algorithm searches for the longest path to reach this node. In this case, there is only one possible way to reach it, which automatically is the longest possible path to travel (maximum) (Picture 1). The same count for the node $S_{2}$ (Picture 2).

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \lambda_1^*= max\{\lambda_0^* + t_{0,1}\}=2; M_1^* = \{S_0\}

and                 

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \lambda_2^*= max\{\lambda_0^* + t_{0,2}\}=1; M_2^* = \{S_0\}

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

---

However, at node $S_{3}$ there are 3 different possibilities, namely by traveling either $S_{0}$, $S_{1}$ or $S_{2}$. The longest path leads over node $S_{0}$, so this is the node which is chosen and $M3$ is set as $S_{0}$ (Picture 3).

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \lambda_3^*= max\{\lambda_0^* + t_{0,3};\lambda_1^* + t_{1,3};\lambda_2^* + t_{2,3}\}= max\{5;4;3\}=5; M_3^* = \{S_0\}

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

---

The next step is regarding node $S_{4}$, for which $S_{2}$ and $S_{3}$ are the possible predecessors, with distances of 8 (1+7) and 11 (5+6) respectively from the starting point. 11 is larger than 8, so the chosen predecessor node of $S_{4}$ is $S_{3}$. (Picture 4).

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \lambda_4^*= max\{\lambda_2^* + t_{2,4};\lambda_3^* + t_{3,4}\}= max\{8;11\}=11; M_4^* = \{S_3\}

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

---

$S_{5}$ can be reached by passing $S_{3}$ or $S_{1}$, the longest path is provided by travelling $S_{1}$ (2+6=) 8 > 7 (=2+5). (Picture 5).

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \lambda_5^*= max\{\lambda_1^* + t_{1,5};\lambda_3^* + t_{3,5}\}= max\{8;7\}=8; M_5^* = \{S_1\}

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

---

$S6$ can be reached over $S1$ or $S5$, with distances of 7 and 10, respectively. The path by using $S1$ with a complete distance of 10 is larger than the path by using $S3$ (distance of 7). (Picture 6).

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \lambda_6^*= max\{\lambda_1^* + t_{1,6};\lambda_5^* + t_{5,6}\}= max\{7;10\}=10; M_6^* = \{S_5\}

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

---

At the ending-node $S7$, there are 3 different possibilities to reach it, using $S4$, $S5$ or $S6$ as predecessor. In this case, we have two identical maxima, namely travelling $S5$ or $S4$ with an overall distance of 15 both. As a conclusion, we have the special case of two different longest (or critical) paths:

$S0$, $S3$, $S4$, $S7$ or

$S0$, $S1$, $S5$, $S7$ (Picture 7).

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \lambda_7^*= max\{\lambda_4^* + t_{4,7};\lambda_5^* + t_{5,7};\lambda_6^* + t_{6,7}\}= max\{15;15;14\}=15; M_7^* = \{S_4,S_5\}

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

---

Refering to the example considering the building, there mustn't appear a delay in the stages which are part of the critical path. Otherwise, the completion of the whole building would retard. The two critical paths in the mathematical example above are the following:

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Literature

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \bullet

Dorninger, Dietmar W.; Karigl, Günther: Mathematik Für Wirtschaftsinformatiker: Grundlagen, Modelle, Programme, Band 1. Wien 1988, ISBN 978-3211820476

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \bullet

http://en.wikipedia.org/wiki/Longest_path_problem

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \bullet

http://de.wikipedia.org/wiki/Bellman-Ford-Algorithmus