Just putting it out there, this is a homework question but I wanted to get a second opinion on my thoughts to see if my thought process was right.
Say we have an undirected graph $G = (V,E)$. We know that Floyd-Warshall algorithm finds all shortest paths (least weight) in a graph given G does not have negative cycles.
So, suppose we have a graph that does have a negative cycle. The question asks, is there an algorithm that we can create to enable Floyd-Warshall to work on this graph?
My logic: If we have a graph with a negative cycle in it, there is a finite smallest (most-negative) weight (i.e. there is a weight of $-4$ on an edge and no edge has a weight less than $-4$). Therefore, in $O(|E|)$ time, I traverse the graph to find the smallest weight. Then, I can add the absolute value of the smallest weight to each edge. We would alter the graph by adding this smallest weight to each edge. Thus, there will not be any negative cycles as each weight should now be positive. We can now run Floyd-Warshall on our graph.
As far as my logic goes, are there any flaws that are obvious? Would this be a viable solution?
Best Answer
Adding a constant to the weights of all edges does not preserve the relative order of paths.
For example, a path with edge weights $1,2,3$ is better than a path with edge weights $4,5$, since $1+2+3=6$ and $4+5=9$. But if you find an edge with weight $-10$ and add $10$ to every edge to fix this, the first path now weights $11+12+13 = 36$ and the second one only weighs $14+15 = 29$.
You might also ask what it means to even have a shortest path in a graph with negative edge cycles, given that we can find such a cycle, go around it a billion times, and then keep going.