Actually, I have two questions on this algorithm, I hope for your help. 1) The graph is given by the adjacency matrix, it is necessary to find vertices between which there exists an arbitrarily small path (i.e. there are negative weight cycles). Here is a piece of code:

d - adjacency matrix, INF = 1e1000, it is necessary to write a two to array a if there is an arbitrarily small path between i and j.

for (int k=0; k<n; ++k) for (int i=0; i<n; ++i) for (int j=0; j<n; ++j) { if (d[i][j] > d[i][k] + d[k][j]) { d[i][j] = d[i][k] + d[k][j]; if(d[i][k] < INF && d[k][j] < INF && d[k][k] < 0) a[i][j] = 2; } }

The code does not work correctly, what is my mistake? I used this material:

There are negative weight cycles in the graph.

In this case, between some pairs of vertices there can be an arbitrarily short path. Finding such pairs is simple in a matrix of “shortest” paths constructed by the Floyd algorithm. There are statements:

If there is a cycle of negative weight passing through vertex i, then ai, i will be less than 0. Between a pair of vertices (i, j) there exists an arbitrarily small path if and only if there is a path from i to j containing a cycle of negative weight or in other words, there is a vertex k such that there is a path from i to k, from k to j and there is a cycle of negative weight passing through k

2) It is necessary to find the maximum paths between all pairs of vertices. I tried this: I filled the adjacency matrix opposite to the entered distances and used the following code:

 for (int k=0; k<n; ++k) for (int i=0; i<n; ++i) for (int j=0; j<n; ++j) { if (d[i][j] < d[i][k] + d[k][j]) { d[i][j] = d[i][k] + d[k][j]; } }

No sense ... What are my mistakes?



    1 answer 1

    After the Floyd's algorithm works, in the matrix d, for each vertex i, the length of the minimum path to each vertex j = 1..n will be stored (n is the number of vertices). Therefore, the answer to your first question looks like this:

     for (int k=0; k<n; ++k) for (int i=0; i<n; ++i) for (int j=0; j<n; ++j) { if (d[i][j] > d[i][k] + d[k][j]) { d[i][j] = d[i][k] + d[k][j]; if(d[i][j] < 0) a[i][j] = 2; } }

    Answer to the second question: It is necessary either to write opposite values ​​into the adjacency matrix, or to change the> sign in if (d[i][j] > d[i][k] + d[k][j]) to <, but not two options together, otherwise it turns out the same thing as finding the minimum way :).