CODEWITHSUNDEEP
algorithmgraph-algorithmfloyd-warshall
xodos
xodos

Reputation: 49

Upside down Floyd–Warshall

I have a quick question. I know that this is a problem NP. If you receive the correct reversal algorithm Floyd-Warshall longest path between each pair of nodes?

Upvotes: 0

Views: 737

Answers (1)

user555045
user555045

Reputation: 64904

That doesn't work. The problem is that the structure of the longest path problem is fundamentally different.

It's not very obvious perhaps, but Floyd-Warshall uses the optimal substructure property of the shortest path problem. That is, the shortest path from A to B through C is made out of the shortest path from A to C and the shortest path from C to B.

The longest path problem does not have that property, you can see this quite obviously in a 3 node example:

    A
   / \
  B---C

The longest path (recall that LPP asks for a simple path, so it's still well-defined in the presence of cycles) from A to B is obviously A,C,B (or more generally, the longest path anywhere has length 2), but the longest paths from A to C and B to C both include A, so the pieces can't even combine to form valid paths. That is a problem in general - if you try to build a complete longest path out of two sub-paths, the sub-paths have to "know" about each other so they won't repeat nodes.

Of course you can also very easily show that LPP is NP-hard (with reduction from the Hamiltonian path problem), which doesn't prove that it cannot be solved in polynomial time, but if it seems you have done so you should be rather suspicious of the result. It is after all not very likely that we just casually solve the P ?= NP problem on a spare afternoon, especially not in an obvious way.

Upvotes: 1

Related Questions