Longest paths: Dijkstra 2: Unterschied zwischen den Versionen

Version vom 30. Juni 2013, 22:06 Uhr

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 can choose B or C as next base node. In this case we choose C because it has the longest distance to A. The actual distance is 7. (A-C = 7)

Step 2:

Select the most distant node from A as next base node (C) and repeat step 2 from above. We have not reached the goal node (G) yet, so we continue with the next Base node C and calculate all paths from node C to the neighbour nodes. We choose the Path A-C-F and F as next base node. (C-E = 11) and C (C-F = 15).

Step 3:

The next iteration step from base node F leads to our goal node G. Our temporary longest path is A-C-F-G with 20.

Step 4 and 5:

Now we have to check if there are any paths that have a longer distance than A-C-F-G. So we take the second distant node from A (In this Case E) and calculate the paths to all neighbour nodes as before. A-C-E-F is shorter than A-C-F and therefore we reject this path. A-C-E-D is stored with the path length of 12.

D is our next base node and we calculate the path to our goal node G (A-C-E-D-G). The length is 16 and shorter than A-C-F-G therefore we have to reject it.

Step 6:

We continue with the next distant node from A (node B)and repeat the calculation. A-B-E is shorter than A-C-E and therefore we reject this path. A-B-D has the same length as A-C-E-D, we can decide which path we want to keep. We have considered all paths of this graph and found the longest path is A-C-F-G (20)

Longest Path

The longest path is A-C-F-G with 20.

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.