I'm having some problems with this. First, i used Floyd-warshall to show all min cycles on a directed graph and it worked, but then I tried using it with undirected graph and it doesn't work like I need.
For example, lets say I have this graph:
INF INF 19 14 8
INF INF 13 INF 9
19 13 INF INF 3
14 INF INF INF 10
8 9 3 10 INF
This should look something like this:
Anyway, since you can represent a undirected graph as a directed graph (just like i did in the example matrix), Floyd Warshall should work, but the results aren't what I expected. Using the same graph example, this is the matrix with the min path cost:
Min path cost:
16 17 11 14 8
17 18 12 19 9
11 12 6 13 3
14 19 13 20 10
8 9 3 10 6
And this is the matrix with the path:
(0 4 0) (0 4 1) (0 4 2) (0 3) (0 4)
(1 4 0) (1 4 1) (1 4 2) (1 4 3) (1 4)
(2 4 0) (2 4 1) (2 4 2) (2 4 3) (2 4)
(3 0) (3 4 1) (3 4 2) (3 4 3) (3 4)
(4 0) (4 1) (4 2) (4 3) (4 2 4)
Since im interested just in cycles, I only need the matrix's diagonal here.
Anyway, lets take 0 - > 0: the result is (0 4 0) which cost is 16
Anyway, since Im looking for min cycles I expected something like:
0 -> 0, Path (0 4 2 0) (or 0 2 4 0 since is a undirected graph, but I just need one of them) and cost 30.
This is the floyd-warshall code in fact:
for (k = 0; k < V; k++)
{
for (i = 0; i < V; i++)
{
for (j = 0; j < V; j++)
{
if (dist[i][k] != INF && dist[k][j] != INF &&
dist[i][k] + dist[k][j] < dist[i][j]) {
dist[j][i] = dist[i][j] = dist[i][k] + dist[k][j];
path[i][j] = path[j][i] = path[k][j];
}
}
}
}
I really don't know what I need to change to get the right result (or maybe that is the right result and I think isn't).
