Let say I have a directed graph G with positive edges and I create a new graph, G', by replacing the weight of each edge by the negation of its weight in G. If for a given source vertex s, I compute all shortest path from s in G' using Dijkstra’s algorithm. Will the resulting paths in G’ be the longest (i.e., highest cost) simple paths from s in G. True or false? And please, justify.

  • 3
    $\begingroup$ What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. I suggest you try working through a few examples of small graphs $G$ and see what happens, see if you can spot a pattern, formulate a conjecture, and see if you can prove or disprove it. $\endgroup$ – D.W. Apr 23 '17 at 17:11

The answer is FALSE.

Contradicting example: (starting from S)

enter image description here

Running Dijkstra on the following graph will not find the longest path from S to D (S->A->B->C->D). Due to removing node C from the queue too soon (before the relaxation of node B), hence prev(D) = E.

Please follow the correctness argument of Dijkstra's algorithm, which relies heavily on the edge weights being positive.

In addition, longest path problem is computationally hard. (NP-Hard).

  • $\begingroup$ A simpler graph example: $w(S \to A) = 2, w(S \to B) = 1, w(B \to A) = 2$. $\endgroup$ – hengxin Apr 25 '17 at 7:46
  • $\begingroup$ What about an acyclic graph? $\endgroup$ – Meepo Oct 23 '19 at 6:30

The answer to your question is plain yes and proving it is really simple.

If $\pi$ is a shortest path in $G'$ then by hypothesis there is no path $\pi'$ in $G'$ such that $c(\pi')<c(\pi)$, where $c(\cdotp)$ is the cost of a path. Now, by negating the edge weights the opposite can be asserted in the original graph $G$, and there is no path $\pi'$ in $G$ such that $c(\pi')>c(\pi)$, i.e., $\pi$ is the longest path in $G$.

I wanted to answer your question to post another very interesting question that results from considering this answer (which I think is what really lies at the core of your question):

Is it equally hard/easy to compute shortest paths in $G$ than in $G'$?

  • $\begingroup$ If we use Dijkstra's algorithm in $G'$, will it give us the shortest paths in $G'$? Can you prove it? $\endgroup$ – D.W. Apr 25 '17 at 1:01
  • $\begingroup$ That is actually the question I posted in my answer: one can run Dijkstra in the original graph $G$ to compute the shortest path, but what if all weights are negative? In my answer I only proved that the shortest path in $G'$ is the longest path in $G$ as stated in the original question. Explicitly, I did not want to consider Dijkstra as I assumed that was part of an exercise. $\endgroup$ – Carlos Linares López Apr 25 '17 at 9:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy