There is a connected undirected graph, given by the adjacency matrix, which is processed by the Floyd-Worshell algorithm. Given that the edges between the vertices may not be (then they are given as -1 ), we get the following algorithm:

 for(i=0;i<n;i++) for(j=0;j<n;j++) for(l=0;l<n;l++) if ((d[i][l]>d[i][j]+d[j][l]||d[i][l]<0)&&d[i][j]>=0&&d[j][l]>=0) d[i][l]=d[i][j]+d[j][l];

It seems to be all right, but for some reason several edges are not processed.

For example, processing the graphs given by such a matrix:

  0 -1 1 2 -1 0 -1 5 1 -1 0 4 2 5 4 0

The result is:

 0 7 1 2 7 0 9 5 1 8 0 3 2 5 3 0

Ie it is unknown how the length of the edge 9 appears.

What is the problem? Where is the error in writing the algorithm?

    2 answers 2

    The outer loop must be in l , inner in i and j .

    • Please explain why? - Crasher
    • 2
      by the fact that i and j are pairs of vertices (from and to which we are looking at the path), and l is the vertex that we add during the new pass and it should be added only after the algorithm has checked all the paths with the previous vertex (well, if you understand algorithm, and I think you understand) - rasmisha
    • Thank you very much! Before this question, I thought that the order does not matter and changes only the "direction of work" of the algorithm (from the end to the beginning, for example), but it turned out that this is not at all the case. - Crasher

    Usually in the case when there is no edge between the vertices, indicate some "infinity" INF, and then the code takes the following form:

     for (int k=0; k<n; ++k) for (int i=0; i<n; ++i) for (int j=0; j<n; ++j) if (d[i][k] < INF && d[k][j] < INF) d[i][j] = min (d[i][j], d[i][k] + d[k][j]);

    UPD: Regarding an error in general, you will have a strange relaxation, for Floyd-Worshell, for all pairs of vertices, an attempt is made to facilitate the transition using the third vertex, and in your cycles, everything is completely different, the result is that Floyd-Worthall cannot be called

    • in theory, specifying infinity in this case is the same as specifying -1 , only instead of checking whether the edge is smaller than infinity, it is checked whether it is positive. It is also undesirable to use the min function, since more time is used to perform it. Is it possible to make this algorithm with the same conditions that I described? I just don’t want to just rewrite a piece of code, I’m curious to know what the problem is exactly my version :) - Crasher
    • Specify infinity or -1 is not the same. - Kozlov Sergei
    • Regarding an error in general, you will have a strange relaxation, at Floyd-Worshell, for all pairs of peaks, an attempt will be made to facilitate the transition using the third vertex, and in your cycles, everything is completely different, the result is that you cannot call Floyd-Worshell - Kozlov Sergei
    • In this case, there is no difference. If you specify infinity - we will check if the lengths of the edges go abroad - that is, they are not greater than infinity. If we leave -1 , then we check whether the border belongs in another way - the border in this case is negative numbers. If we slightly modify and compare the conditions in these two methods, their similarity is clearly visible. Is not it? - Crasher
    • // condition when using -1 as no edge if (d [i] [j]> = 0 && d [j] [l]> = 0) if (d [i] [l]> d [i] [j ] + d [j] [l] || d [i] [l] <0) d [i] [l] = d [i] [j] + d [j] [l]; // condition for using infinity as the absence of an edge if (d [i] [k] <INF && d [k] [j] <INF) d [i] [j] = min (d [i] [j], d [i] [k] + d [k] [j]); The only difference is in the boundaries (as I wrote) and in a slightly different use of the function min - Crasher