Найдите кратчайший путь с помощью алгоритма Флойда

У меня есть матрица смежности, которая содержит числа 0 и 1. Если нет ребра от одного узла к другому, поле будет равно 0, в противном случае поле будет помечено как 1.

Тогда, если поле в матрице смежности было 0, между узлами нет ребра, иначе есть ребро с весом 1.

Теперь я применил алгоритм Флойда, чтобы найти кратчайший путь от любого узла к каждому другому узлу. Но я не нашел правильного решения.

Вот моя реализация алгоритма Флойда.

void Floyd_Warshal(int graph[Nodes][Nodes], int D[Nodes][Nodes])
{
    for (int i = 0; i < Nodes; i++)
    {
        for (int j = 0; j < Nodes; j++)
        {
            if (graph[i][j] == 0) { graph[i][j] = INT_MAX; }
            D[i][j] = graph[i][j];
        }
    }
    for (int k = 0; k < Nodes; k++) {
        for (int i = 0; i < Nodes; i++)
        {
            for (int j = 0; j < Nodes; j++)
            {
                if (D[i][j] > D[i][k] + D[k][j]) {
                    D[i][j] = D[i][k] + D[k][j];
                }
            }
        }
    }
}

Я установил 0 как INT_MAX, чтобы построить стандартную матрицу для алгоритма, но я не получил правильного решения.

Также вот пример моей матрицы:

  A B C D
A 0 0 1 0
B 1 1 0 1
C 0 0 1 0
D 1 0 0 0

После применения матрицы к алгоритму любой 0 в матрице будет преобразован в INT_MAX. Я ожидаю получить вес как 2 или 1, но получаю неожиданные значения, такие как -2712323 ...


c++ graph algorithm shortest-path floyd-warshall
person VCL_D    schedule 25.06.2015    source источник
comment
можете ли вы также приложить пример матрицы смежности?   -  person ralzaul    schedule 25.06.2015
comment
... и ожидаемый результат, и результат, который вы получите. Также не могли бы вы прояснить, что вы имеете в виду, говоря: «Если нет ребра от конкретного узла к любым другим узлам, в поле будет 0, иначе поле будет помечено как 1.   -  person Petr    schedule 25.06.2015
comment
@ralzaul Я обновил пост, чтобы добавить пример.   -  person VCL_D    schedule 25.06.2015
comment
@Petr Я имею в виду, что, например, если нет края между узлом A и узлом C, значение A-C в матрице будет 0, иначе значение будет 1.   -  person VCL_D    schedule 25.06.2015
comment
@VCL_D, я немного изменил формулировку вашего вопроса, чтобы он был более ясным, потому что, когда вы используете любые другие узлы, это выглядит так, как будто вы имеете в виду все другие узлы, а не только конкретный другой узел, соответствующий этот элемент в матрице смежности.   -  person Petr    schedule 25.06.2015
comment
@Petr Спасибо за помощь :)   -  person VCL_D    schedule 25.06.2015

Ответы (1)


arrow_upward
5
arrow_downward

Причина, по которой вы получаете очень большие отрицательные значения, - это целочисленное переполнение.

Если края нет, вы устанавливаете D[i][j]=INT_MAX. Но потом

            if (D[i][j] > D[i][k] + D[k][j]) {
                D[i][j] = D[i][k] + D[k][j];

если нет края от i до k и от k до j, тогда сумма будет переполнена и результат будет отрицательным. Впоследствии ваш алгоритм будет думать, что существует очень короткий (большой отрицательный) путь от этого i к этому j, и это отравит все остальные пути.

Я предлагаю вам использовать INT_MAX/2 вместо INT_MAX.

person Petr    schedule 25.06.2015
comment
(или напишите тест как if (D[i][j] - D[k][j] > D[i][k]) {, который не может выходить за пределы, предполагая неотрицательные расстояния.) - person David Eisenstat; 25.06.2015