Reputation: 47
I know that if there are negative cost cycles in a graph, the relative shortest path problem belongs to the np-complete class. I need to prove this by performing a polynomial reduction using the Hamiltonian cycle problem. Could anyone explain it? It would be very helpful.
Upvotes: 0
Views: 527