4

Собственно у меня два вопроса по данному алгоритму, надеюсь на вашу помощь. 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];
                }
             }

Толку нет ... В чем мои ошибки?

1 ответ 1

2

После работы алгоритма Флойда в матрице d будет для каждой вершины i храниться длина минимального пути до каждой вершины j=1..n (n - кол-во вершин). Следовательно, ответ на первый ваш вопрос выглядит так:

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;
            }
         }

Ответ на второй вопрос: Необходимо либо записать в матрицу смежности противоположенные значения, либо сменить знак > в if (d[i][j] > d[i][k] + d[k][j]) на знак <, но не два варианта вместе, иначе получается тоже самое, что и поиск минимального пути :).

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.