0

I am looking at the Floyd-Warshall algorithm. 

let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)

// part 1 
for each vertex v
   dist[v][v] ← 0

// part 2
for each edge (u,v)
   dist[u][v] ← w(u,v)  // the weight of the edge (u,v)

// part 3
for k from 1 to |V|
   for i from 1 to |V|
      for j from 1 to |V|
         if dist[i][k] + dist[k][j] < dist[i][j] then
            dist[i][j] ← dist[i][k] + dist[k][j]

In the page, it says the Floyd–Warshall algorithm assumes that there are no negative cycles. So my question is what will happen if the entry graph hides negative circle. Will the output dist represents another graph hiding negative circle? Does not part 1 invalid this?

SoftTimur
  • 5,630
  • 38
  • 140
  • 292
  • Did you finish reading that section of the Wikipedia article? (http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm#Behavior_with_negative_cycles). It tells you how to detect negative cycles. – Oliver Charlesworth Jun 03 '13 at 14:06
  • Yes, I did (Btw, I have put [another question](http://stackoverflow.com/questions/16898416/fastest-algorithm-to-detect-if-there-is-negative-circle-in-a-graph). The thing is I don't want to put the `detection` and the `normalization` together. I would hope a `normalization` always hold: a graph with negative circle is reduced to another graph with negative circle. – SoftTimur Jun 03 '13 at 14:10
  • But the output of FW isn't a graph, it's a distance matrix. – Oliver Charlesworth Jun 03 '13 at 14:17
  • For me, a `graph` and a `distance matrix` are quite same... I just modified my OP a little bit... – SoftTimur Jun 03 '13 at 14:28
  • Yes, I suppose you could view the matrix as another graph. But that's not really necessary to answer your question... – Oliver Charlesworth Jun 03 '13 at 14:32
  • Apologies, as has been pointed below, I was thinking of Bellman-Ford, not Floyd-Warshall... – Oliver Charlesworth Jun 03 '13 at 15:14

2 Answers2

0

Floyd-Warshall algorithm is for find the shortest path. If negative circle exist, there is no shortest path(you can find a infinitely small(negative) path).

If negative circle exists then what will happen? I will say the output of Floyd means nothing, that is to say, that algorithm doesn't work(since there is no shortest path, how it can work?).

0

Floyd-Warshall algorithm is a label correcting algorithm capable of finding all source to all sink shortest paths. If negative circle exist, there is no shortest path defined. As the shortest path will contain infinite circulations over negative cycles and hence shortest path has unbounded or infinite cost/weight(whatever you call it).

Floyd-Warshall algorithm has two advantages over dijkstra.

  1. Capable of detecting negative cycles. If found, then no shortest path is defined for some pair of nodes. (While some nodes might have a definite finite shortest path, it may not be unique tho).

  2. Capable of finding all source nodes to all sink shortest paths.

(Note that Dijkstra can still achieve the same with even better time complexity but has a constraint that it cannot handle negative edges in the network).

My claim 1: How do I know a negative cycle exist and terminate the algorithm?? Explaination: Whenever a negative cycle is found, for some node i, the shortest path from i to i will become negative. That will indicate a negative cycle exists in graph. So, the algorithm is capable of detecting negative cycles.

Refer to: Chapter 5, Network Flows, by Ahuja, Magnanti & Orlin.

Ayush Tiwari
  • 91
  • 1
  • 8