From Algorithm Wiki
Revision as of 19:57, 5 October 2019 by Tcaner (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
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.