Diskussion:Longest paths: Dijkstra 2

Comment

The longest path problem has a higher NP-hardness (Non-deterministic Polynomial-time hardness), which means that it cannot be solved while satisfying the time restriction of polynomial time. So, the NP-hardness of the longest path problem is higher than the NP-hardness of a shortest path problem, which means that another algorithm than dijkstra is needed. One problem is that we have to avoid cycles which would give an infinite solution. This problem has been considered in your solution. Another problem is that after considering one node it gets a value that cannot be changed anymore. In this simple example the problem is not illustrated obviously, but if the problem becomes more difficult, your modified dijkstra would not always depict the longest path all over the considered graph.