Dijkstra’s in a graph with negation of edges

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.

• 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.
– D.W.
Apr 23, 2017 at 17:11
• cs.stackexchange.com/q/17980/755
– D.W.
Jun 14, 2021 at 5:45

• A simpler graph example: $w(S \to A) = 2, w(S \to B) = 1, w(B \to A) = 2$. Apr 25, 2017 at 7:46