From Algorithm Wiki
Jump to: navigation, search

(Solution 6.20) No, dijkstra's cant be applied to the longest path problem by changing minimum to maximum. By taking the longest possible edge at every iteration, you'd miss certain longer edges that'd make the solution inferior to the most optimal. You can think of it as shortest path with negative edges. The same problem happens there. The problem posed here is fundamentally the same as the Traveling Salesman Problem.