CODEWITHSUNDEEP
graphgraph-theorygraph-algorithmdijkstralongest-path
alienflow
alienflow

Reputation: 410

Longest path in a Graph with Dijkstra

I was just wondering: can you inverse all the weights in a graph and then do a Dijkstra? As we are minimizing the reciprocal values of the weights, the obtained path would maximize it all in all, right? So, in that way, we can obtain the longest path in a graph using Dijkstra! It seems too easy, am I mistaken? Please, enlighten me.

Upvotes: 0

Views: 1155

Answers (2)

MaxPlankton
MaxPlankton

Reputation: 1258

It's easy to understand with a simple example graph.

enter image description here

Suppose you want to go from point A to point D. To minimize the reciprocal values of the weights, you will go through C. But A->B->D is larger.

Edit: Perhaps I should include some math at least.

Suppose the sum of a sequence of positive numbers is s.

a1 + a2 + a3 + ... + an = s.

What's the minimum value of reciprocal sum?

1/a1 + 1/a2 + 1/a3 + ... + 1/an

Playing around this will give you some intuition.

Upvotes: 0

NiVeR
NiVeR

Reputation: 9806

It is not possible to do so because the longest path problem doesn't have the optimal substructure problem as the shortest path one.

Say that you can consider any path as longest path (so it can have cycles) but if there is a cycle and the weights are positive the algorithm will never end since it can always improve the longest path by looping through the cycle.

Now say that we want to have only simple paths (without cycle) as candidates for the longest path. Consider, without loss of generality, the following graph with unitary weights for all edges:

A------B
|      |
|      |
C------D

And consider the longest path from A to D (A->B->D). For the problem to have optimal substructure property it must be the case that longest path from A to Bis A -> B but clearly it isn't because path A->C->D->B is longer. Similar argument can be done for the path from B to D. So we can see why this problem can't be solved with Dijkstra algorithm. As a matter of fact this problem is NP, there isn't a reasonable time complexity solution.

Upvotes: 0

Related Questions