Алгоритм Флойда-Уоршелла

Question

[Kot Matpockuh]

Просьба не пинать меня ногами, и не посылать в дебаг :)

так вот, есть такой граф:

0 8 0 0 10
8 0 4 0 0
0 4 0 6 16
0 0 6 0 2
10  0 16  2 0

и есть такой код, для нахождения кр. путей между вершинами

for (k = 0; k < n; ++k)
            {
                for (i = 0; i < n; ++i)
                    for (j = 0; j < n; ++j)
                        if ((dist[i, k] * dist[k, j] != 0) && (i != j))
                            if ((dist[i, k] + dist[k, j] < dist[i, j]) || (dist[i, j] == 0))
                                dist[i, j] = dist[i, k] + dist[k, j];
            }

не могу понять, что не так, почему к примеру расстояние между 5 и 2 = 18 а не 12 и тд...

Answer 1

[Flaker]

Похоже реализация не совсем верная.

Такая проверка не имеет смысла.
if ((dist[i, k] * dist[k, j] != 0) && (i != j))

Взгляни на e-maxx. Там подробное описание.

Я реализовывал это на C++ таким образом:

#include <iostream>

#define INF 9000000
#define MatrixLen 5

/* Алгоритм Флойда — Уоршелла.*/

/* Исходная матрица расстояний */
int matrix[MatrixLen][MatrixLen] =
{
    {0, 5, 2, INF, INF},
    {5, 0, INF, 7, INF},
    {2, INF, 0, 2, 8},
    {INF, 7, 2, 0, 1},
    {INF, INF, 8, 1, 0}
};

    /* Поиск расстояния минимального пути от каждой до каждой вершины */
    for (size_t k(0); k < MatrixLen; ++k)
        for (size_t i(0); i < MatrixLen; ++i)
            for (size_t j(0); j < MatrixLen; ++j)
                if (matrix[i][k] < INF && matrix[k][j] < INF)
                    if (matrix[i][k] + matrix[k][j] < matrix[i][j])
                        matrix[i][j] = matrix[i][k] + matrix[k][j];


    int from = 0;
    int to = 4;

        /* Теперь минимальное расстояние от любой до любой будет matrix[ОТКУДА][КУДА] */

    std::cout << "Path length from " << from << " to " << to << " is " << matrix[from][to] << std::endl;

Тут существуют вершины, между которыми нет пути. Расстояние между ними при этом задается как INF.

Comments

[Kot Matpockuh]

есть одно но, я не могу использовать inf, в будущем в алгоритме для меня это очень плохо...
Расстояние между ними при этом задается как INF, должно быть 0

[Kot Matpockuh]

т.е. к примеру, здесь я получаю тож самое 18:

[Kot Matpockuh]

dist = G;
for (i = 0; i < n; ++i)
for (j = 0; j < n; ++j)
{
if (i == j)
dist[i, j] = 0;
if (i != j && dist[i, j] == 0)
dist[i, j] = Int32.MaxValue;
}



for (k=0; k < n; ++k)
for (i=0; i < n; ++i)
for (j=0; j < n; ++j)
if (dist[i, k] < Int32.MaxValue && dist[k, j] < Int32.MaxValue)
if (dist[i, k] + dist[k, j] < dist[i, j])
dist[i, j] = dist[i, k] + dist[k,j];
}

[Kot Matpockuh]

@Radiocity ну так он и так 0, просто я ж говорю, код этот что на emaxx, с нулями работает странно!

[Flaker]

Ну в данному случае считается, что 0 это как бы телепортация на место, а не отсутствие пути.

[Kot Matpockuh]

@Flaker кажись начинаю понимать в чём беда, т.к. читаю из файла, а потом присваиваю получается массив не как значения, а как ссылку в памяти

Answer 2

[Rsa97]

Прогнал вашу реализацию с выводом на каждом шаге - всё работает.

Исходный массив
0  8  0  0  10
8  0  4  0  0
0  4  0  6  16
0  0  6  0  2
10 0  16 2  0
-- Шаг 1 -----
0  8  0  0  10
8  0  4  0  18
0  4  0  6  16
0  0  6  0  2
10 18 16 2  0
-- Шаг 2 -----
0  8  12 0  10
8  0  4  0  18
12 4  0  6  16
0  0  6  0  2
10 18 16 2  0
-- Шаг 3 -----
0  8  12 18 10
8  0  4  10 18
12 4  0  6  16
18 10 6  0  2
10 18 16 2  0
-- Шаг 4 -----
0  8  12 18 10
8  0  4  10 12
12 4  0  6  8
18 10 6  0  2
10 12 8  2  0
-- Шаг 5 -----
0  8  12 12 10
8  0  4  10 12
12 4  0  6  8
12 10 6  0  2
10 12 8  2  0

Так что придётся Вам всё же лезть в дебаг и смотреть, что происходит и что идёт не так именно в вашей системе.

Comments

[Kot Matpockuh]

кажись начинаю понимать в чём беда, т.к. читаю из файла, а потом присваиваю получается массив не как значения, а как ссылку в памяти

[Kot Matpockuh]

headshot( вроде ж присваиваю как значения а не как ссылку, но всё равно не хочет, только если инициализировать матрицу явно.