Блог пользователя felipeblassioli

Автор felipeblassioli, история, 9 лет назад, По-английски

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

Apparently it works for directed graphs. Is there a way to modify Floyd-Warshall and find the minimum weight cycle?

The problem with this approach for undirected graphs is:

If your undirected graph is a tree, there are no cycles right? Suppose there is a edge (u,v) whose weight is dist[u][v] = dist[v][u] = 1. (remember that with the 'modification' dist[u][u] = INF and not zero anymore)

The at iteration i = j = u and k = v:

dist[i][j] > dist[i][k] + dist[k][j] => dist[u][u] > dist[u][v] + dist[v][u] => INF > 1 + 1

So dist[u][u] = 2. But the distance from u to itself cant be 2, because the graph has no cycles (it is a tree)!

  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Using Floyd Warshall will work if the graph has directed edges. If the graph is undirected, then the answer will always be 2*minEdge, because for every node you can take one path to another node and return.