Dijkstra’s in a graph with negation of edges
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).