Власне у мене два питання по даному алгоритму, сподіваюся на вашу допомогу. 1) Граф заданий матрицею суміжності, необхідно знайти вершини між якими існує як завгодно малий шлях (тобто присутні цикли негативного ваги). Ось шматок коду:
d - матриця суміжності, INF = 1e1000, в масив a необхідно записати двійку якщо між i і j існує як завгодно малий шлях.
Код не працює належним чином, в чому моя помилка? Я використовував даний матеріал:
У графі є цикли негативного ваги.
У цьому випадку між деякими парами вершин може бути як завгодно короткий шлях. Найі такі пари нескладно по матриці "найкоротших" шляхів, посторенная алгоритмом Флойда. Мають місце твердження:
Якщо існує цикл негативного ваги, що проходить через вершину i, то ai, i буде менше 0. Між парою вершин (i, j) існує як завгодно малий шлях тоді і тільки тоді, коли існує шлях з i в j, що містить цикл негативного ваги або , іншими словами, існує вершина k така, що існує шлях з i в k, з k в j і існує цикл негативного ваги, що проходить через k
2) Необхідно знайти максимальні шляху між усіма парами вершин. Я пробував так: заповнював матрицю суміжності протилежними від вводяться відстаней і використовував такий код:
Толку немає. У чому мої помилки?
Після роботи алгоритму Флойда в матриці d буде для кожної вершини i зберігатися довжина мінімального шляху до кожної вершини j = 1..n (n - кількість вершин). Отже, відповідь на перше ваше питання виглядає так:
Відповідь на друге запитання: Необхідно або записати в матрицю суміжності протилежний значення, або змінити знак> в if (d [i] [j]> d [i] [k] + d [k] [j]) на знак <, но не два варианта вместе, иначе получается тоже самое, что и поиск минимального пути :).