Can we use Floyd-Warshall to find the minimum weight non-trivial cycle in a graph?

Revision en4, by felipeblassioli, 2015-10-08 20:21:43

Can we modify Floyd-Warshall and have dist[u][u] = shortest distance from u to itself?

Floyd-Warshall is initialized with dist[u][u] = 0 , can we do dist[u][u] = INF and run a default implementation of Floyd-Warshall hoping that dist[u][u] is the shortest distance from u to u? (i.e the minimum weight cycle)?

Does this works for both directed and undirected graphs?

I'm taking for a default implementation something like wikipedia:

let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
2 for each vertex v
3    dist[v][v] ← 0
4 for each edge (u,v)
5    dist[u][v] ← w(u,v)  // the weight of the edge (u,v)
6 for k from 1 to |V|
7    for i from 1 to |V|
8       for j from 1 to |V|
9          if dist[i][j] > dist[i][k] + dist[k][j] 
10             dist[i][j] ← dist[i][k] + dist[k][j]
11         end if
Tags algorithms, graphs, help me, cycle, cycle detection, floyd-warshall

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English felipeblassioli 2015-10-08 20:26:20 659 Explanation with problem with undirected graphs
en4 English felipeblassioli 2015-10-08 20:21:43 12 Trivial cycle for undirected graphs are not interesting
en3 English felipeblassioli 2015-10-08 05:11:44 90
en2 English felipeblassioli 2015-10-08 05:07:13 50 Tiny change: '\nFloyd-Wars' -
en1 English felipeblassioli 2015-10-08 04:54:23 834 Initial revision (published)