Backtrack after running Johnson algorithm

1
votes

I have a question which I was asked in some past exams at my school and I can't find an answer to it.

Is it possible knowing the final matrix after running the Johnson Algorithm on a graph, to know if it previously had negative cycles or not? Why?

Johnson Algorithm

Johnson's Algorithm is a technique that is able to compute shortest paths on graphs. Which is able to handle negative weights on edges, as long as there does not exist a cycle with negative weight.

The algorithm consists of (from Wikipedia):

  • First, a new node q is added to the graph, connected by zero-weight edges to each of the other nodes.
  • Second, the Bellman–Ford algorithm is used, starting from the new vertex q, to find for each vertex v the minimum weight h(v) of a path from q to v. If this step detects a negative cycle, the algorithm is terminated.
  • Next the edges of the original graph are reweighted using the values computed by the Bellman–Ford algorithm: an edge from u to v, having length w(u, v), is given the new length w(u,v) + h(u) − h(v).
  • Finally, q is removed, and Dijkstra's algorithm is used to find the shortest paths from each node s to every other vertex in the reweighted graph.

enter image description here

2
algorithmgraph-algorithmshortest-pathdijkstrabellman-ford
Can you elaborate on your question a bit more? Maybe make an example. That way your question reaches more people, is easier to understand, self-contained and helps more people finding your question. - Zabuzard
Did you mean to say "if it previously had negative edges" instead of "if it previously had negative cycles"? Because Johnson's algorithm aborts if there are negative cycles. - Matt Timmermans
Yes, my bad, negative edges. I don't know how to elaborate more because this is how i found the question, and I'm confused too. - Stefan Chelbosu
"knowing the final matrix" - you mean knowing the distances matrix? - ShaharA
Do you agree with @ShaharA's suggestion or does "final matrix" refer to the updated non-negative edge weights? If the latter then no you can't tell, because running Johnson on a graph with non-negative weights leaves them unchanged. - myrtlecat

2 Answers

0
votes

If I understood your question correctly, which should have been as follows:

Is it possible knowing the final pair-wise distances matrix after running the Johnson Algorithm on a graph, to know if it originally had any negative-weight edges or not? Why?

As others commented here, we must first assume the graph has no negative weight cycles, since otherwise the Johnson algorithm halts and returns False (due to the internal Bellman-Form detection of negative weight cycles).

The answer then is that if any negative weight edge e = (u, v) exists in the graph, then the shortest weighted distance between u --> v cannot be > 0 (since at the worst case you can travel the negative edge e between those vertices).

enter image description here

Therefore, at least one of the edges had negative weight in the original graph iff any value in the final pair-wise distances is < 0

0
votes

If the question is supposed to be interpreted as:

Is it possible, knowing the updated non-negative edge weights after running the Johnson Algorithm on a graph, to know if it originally had any negative-weight edges or not? Why?

Then no, you can't tell.

Running the Johnson algorithm on a graph that has only non-negative edge weights will leave the weights unchanged. This is because all of the shortest distances q -> v will be 0. Therefore, given the edge weights after running Johnson, the initial weights could have been exactly the same.