Cheers, I am trying to solve the problem of minimum length cycle in a directed 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 visualizing the process, using this website here, I generated a graph which contained many cycles inside it, but although the diagonal is initialized with infinity, it does not get changed. Can anyone explain what am I missing or what I can do to solve my problem?
For directed graphs, the idea is that you're just changing your path matrix so that, instead of storing the length of shortest path from i to j, path[i][j] stores the length of the shortest non-empty path, i.e., it only includes paths with at least one edge. Of course that only affects paths from a vertex to itself.
So now, we initialize path[i][i] with infinity instead of 0, because we haven't at that time found any non-empty paths from the vertex to itself.
We then do the normal Floyd-Warshall iterations after initializing the rest of the matrix according to the edges:
for k in |V|:
for j in |V|:
for i in |V|:
path[i][j] = min(path[i][j], path[i][k] + path[k][j])
Lets say there is a simple cycle 1 -> 2 -> 1. Then, when (i,j,k) == (1,1,2), we do path[1][1] = min(path[1][1], path[1][2] + path[2][1])
This changes path[1][1] from infinity to the cycle length.
If you modified an implementation and it doesn't do this, then that implementation was probably optimized to ignore the diagonal altogether.