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.
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).