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

Question

У меня есть матрица смежности, которая содержит числа 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...

Answer 1

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

Если нет края, вы устанавливаете 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,