Longest paths: Dijkstra 2: Unterschied zwischen den Versionen

Version vom 29. Juni 2013, 14:56 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 with some simple modifications.

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