Собственно у меня два вопроса по данному алгоритму, надеюсь на вашу помощь. 1) Граф задан матрицей смежности, необходимо найти вершины между которыми существует сколь угодно малый путь (т.е. присутствуют циклы отрицательного веса). Вот кусок кода:
d - матрица смежности, INF = 1e1000, в массив a необходимо записать двойку если между i и 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;
}
}
Код работает неправильно, в чем моя ошибка? Я использовал данный материал:
В графе есть циклы отрицательного веса.
В этом случае между некоторыми парами вершин может быть сколь угодно короткий путь. Найи такие пары несложно по матрице "кратчайших" путей, посторенных алгоритмом Флойда. Имеют место утверждения:
Если существует цикл отрицательного веса, проходящий через вершину i, то ai,i будет меньше 0. Между парой вершин (i,j) существует сколь угодно малый путь тогда и только тогда, когда существует путь из i в j, содержащий цикл отрицательного веса или, иными словами, существует вершина k такая, что существует путь из i в k, из k в j и существует цикл отрицательного веса, проходящий через k
2) Необходимо найти максимальные пути между всеми парами вершин. Я пробовал так: заполнял матрицу смежности противоположными от вводимых расстояний и использовал такой код:
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];
}
}
Толку нет ... В чем мои ошибки?