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.
$\begingroup$
$\endgroup$
2
-
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. ♦Commented Apr 23, 2017 at 17:11
-
$\begingroup$ cs.stackexchange.com/q/17980/755 $\endgroup$– D.W. ♦Commented Jun 14, 2021 at 5:45
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
The answer is FALSE.
Contradicting example: (starting from S)
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$– hengxinCommented Apr 25, 2017 at 7:46
-
1