Algorithm for modifying graph with negative cycles to be able to conduct Floyd-Warshall

by RocktheWhiteGold   Last Updated October 12, 2018 01:20 AM

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?

Related Questions

Constructing a random bipartite graph

Updated January 11, 2017 08:08 AM