Longest paths: Dijkstra 4: Unterschied zwischen den Versionen
Aus Operations-Research-Wiki
| [unmarkierte Version] | [unmarkierte Version] |
Glad (Diskussion | Beiträge) |
Glad (Diskussion | Beiträge) (→1. Theory) |
||
| Zeile 3: | Zeile 3: | ||
== '''1. Theory''' == | == '''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. | + | 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. | ||
Version vom 1. Juli 2013, 16:44 Uhr
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.
