0
$\begingroup$

Cheers, I am trying to solve the problem of minimum length cycle in a graph, and I came across a solution that suggested that I should tweak the Floyd-Warshall algorithm to solve that. It stated that instead of setting path[i][i] = 0 I should instead set path[i][i] = INFINITY, but I don't exactly understand why that is the case! I find that the main diagonal of the array used by Floyd-Warshall does not change, so how can it help me to see the path of the cycle? I understand that the generated array of the algorithm helps me find the shortest path of a pair. e.g. path[i][j] gives me the shortest path from i to j but, although the intuition stays the same, I see that nothing changes, and I can't take the desired result.

I even tried visualing the process, as seen here. I generated the graph below:

graph

but as you can see, although the diagonal is initialized with infinity, it does not get changed, even though the graph clearly has cycles. Can anyone explain what am I missing?

$\endgroup$

1 Answer 1

2
$\begingroup$

If you let it, running the algorithm will produce, in path[i][i], the length of the shortest path from node i to i. The length of the shortest cycle will be the smallest value on the diagonal. This requires

  • updating path[i][i], instead of skipping it, like that visualization does;
  • initializing path[i][i] with the actual cost of going from that node to itself in one step: the cost of a self-loop, or if there is no self-loop, infinity.

Initializing the diagonal with 0s will leave it at all 0s, even when you don't skip updating it.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.