Floyd-Warshall algorithm

Question

Algorithms

Please do not kick me with your feet, and do not send me to the debug :)
and so, there is such a graph:

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

and there is such a code for finding kr. paths between peaks

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

I can't figure out what's wrong, why, for example, the distance between 5 and 2 = 18 and not 12, etc...

Answer 1

It looks like the implementation is not quite correct.
Such a check is meaningless.
Take a look at e-maxx . There is a detailed description.
I implemented it in C++ like this:

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

There are peaks between which there is no way. The distance between them is given as INF.

Answer 2

I ran your implementation with output at each step - everything works.

Исходный массив
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

So you still have to get into the debug and see what is happening and what is going wrong exactly in your system.