Флойд-Уоршалл не может понять, что не так

Мне нужна новая пара глаз для этого, по какой-то причине она не генерирует правильные матрицы последовательности и расстояния. Ниже приведена моя реализация.

Это в С#, а DistanceMatrix — это двойной [,] а SequenceMatrix — это строка [,]

они инициируются следующим образом: http://puu.sh/951Tz/5ef27e3996.png

for (int k = 0; k < villageCount; k++)
        {
            for (int i = 0; i < villageCount; i++)
            {
                if (k == i)
                    continue;

                for (int j = 0; j < villageCount; j++)
                {
                    if (j == i)
                        continue;

                    if (j == k)
                        continue;

                    if (fw.DistanceMatrix[i, j] >= (fw.DistanceMatrix[i, k] + fw.DistanceMatrix[k, j]))
                    {
                        fw.DistanceMatrix[i, j] = (fw.DistanceMatrix[i, k] + fw.DistanceMatrix[k, j]);
                        fw.SequenceMatrix[i, j] = fw.SequenceMatrix[k, j];
                    }
                }
            }
        }

по какой-то причине я получаю следующий вывод:

    [0, 0]  "A" string
    [0, 1]  "B" string
    [0, 2]  "A" string
    [0, 3]  "B" string
    [0, 4]  "D" string
    [1, 0]  "B" string
    [1, 1]  "D" string
    [1, 2]  "D" string
    [1, 3]  "B" string
    [1, 4]  "D" string
    [2, 0]  "B" string
    [2, 1]  "B" string
    [2, 2]  "B" string
    [2, 3]  "B" string
    [2, 4]  "D" string
    [3, 0]  "B" string
    [3, 1]  "B" string
    [3, 2]  "C" string
    [3, 3]  "C" string
    [3, 4]  "D" string
    [4, 0]  "B" string
    [4, 1]  "E" string
    [4, 2]  "D" string
    [4, 3]  "B" string
    [4, 4]  "E" string

любые указатели будут высоко оценены, также, если вам потребуется дополнительная информация, я буду F5ing на этой странице :)

матрица расстояний после инициализации

    [0, 0]  0.0                                 double
    [0, 1]  50.0                                    double
    [0, 2]  2.0                                 double
    [0, 3]  10.0                                    double
    [0, 4]  1.7976931348623157E+308 double
    [1, 0]  50.0                                    double
    [1, 1]  0.0                                 double
    [1, 2]  3.0                                 double
    [1, 3]  1.7976931348623157E+308 double
    [1, 4]  1.0                                 double
    [2, 0]  2.0                                 double
    [2, 1]  3.0                                 double
    [2, 2]  0.0                                 double
    [2, 3]  5.0                                 double
    [2, 4]  5.0                                 double
    [3, 0]  10.0                                    double
    [3, 1]  1.7976931348623157E+308 double
    [3, 2]  5.0                                 double
    [3, 3]  0.0                                 double
    [3, 4]  1.7976931348623157E+308 double
    [4, 0]  1.7976931348623157E+308 double
    [4, 1]  1.0                                 double
    [4, 2]  5.0                                 double
    [4, 3]  1.7976931348623157E+308 double
    [4, 4]  0.0                                 double

c# algorithm floyd-warshall
person Oliver Ciappara    schedule 28.05.2014    source источник
comment
Какой результат вы ожидаете?   -  person Golden Dragon    schedule 28.05.2014
comment
Это от моего одноклассника, я дал ему снимки экрана моего кода, и нет никаких различий, которые должны повлиять на алгоритм puu.sh/94W63/3733d3275f.png также это карта, если вам интересно puu.sh/954sl/89bd904fda.png если вам интересно это инициация матрицы puu.sh/954Bu/fc0be21893.png   -  person Oliver Ciappara    schedule 28.05.2014
comment
На своем снимке экрана вы говорите, что вы устанавливаете значения в DistanceMatrix до бесконечности, но устанавливаете ли вы затем соответствующие элементы в нем на основе соединений на графике? Часть кода, которую вы разместили, выглядит нормально   -  person Golden Dragon    schedule 28.05.2014
comment
да puu.sh/9554w/5bbe3027fa.png, в настоящее время я прорабатываю все итерации вручную, чтобы сравнить результаты: / если вы можете сэкономить мне время :)   -  person Oliver Ciappara    schedule 28.05.2014
comment
Так как же выглядит матрица расстояний после ее инициализации?   -  person Golden Dragon    schedule 28.05.2014
comment
См. редактирование матрицы расстояний после инициализации   -  person Oliver Ciappara    schedule 28.05.2014
comment
В псевдокоде для этого алгоритма не пропускается, если разные итераторы равны . Пробовали закомментировать эти строки и посмотреть, что получится?   -  person tinstaafl    schedule 28.05.2014
comment
это модификация производительности, и да, я пытался удалить ее, все тот же результат   -  person Oliver Ciappara    schedule 28.05.2014
comment
Подсказка для дальнейшего использования. Обычно стоит сначала заставить ваш код работать, а затем беспокоиться о производительности. Таким образом, у вас всегда будет рабочая базовая линия, к которой можно вернуться.   -  person tinstaafl    schedule 28.05.2014

Ответы (3)


arrow_upward
2
arrow_downward

Я считаю, что нашел проблему.

Вы инициализируете SequenceMatrix неправильно. У вас есть

fw.SequenceMatrix[i, j] = map.Villages.ElementAt(i).Name;

Однако, согласно статье в Википедии, это должно быть

fw.SequenceMatrix[i, j] = map.Villages.ElementAt(**j**).Name;

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

Похоже, в вашем алгоритме тоже есть ошибка. У вас есть

fw.SequenceMatrix[i, j] = fw.SequenceMatrix[k, j];

Но это должно быть

fw.SequenceMatrix[i, j] = fw.SequenceMatrix[**i, k**];

Поскольку вы определили, что движение от i к k и j короче, чем движение от i к j, вы хотите установить первый шаг нового пути от i до j таким же, как первый шаг пути от i до j. к.

person Golden Dragon    schedule 28.05.2014
comment
Итак, вы по-прежнему получаете тот же результат, что и раньше? - person Golden Dragon; 28.05.2014
comment
Нет, с обоими этими изменениями новый вывод выглядит так, что все еще неверно puu.sh/9599j/335a8c0241. png - person Oliver Ciappara; 28.05.2014
comment
Тогда вам придется отладить свой код и пройтись по нему, чтобы увидеть, что именно идет не так. - person Golden Dragon; 28.05.2014
comment
Он делает это с 11 утра - person Oliver Ciappara; 28.05.2014

arrow_upward
1
arrow_downward

Может быть, проблема в том, что inf+inf не в порядке (переполнение)? В любом случае, я думаю, что реализации должны выглядеть как это

// d[i][j] == weight of edge (i,j)
// d[i][j] == INF if there is no such edge
// d[i][i] == 0; i = 0, .., n-1

for (int k = 0; k < n; ++k)
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            if (d[i][k] < INF && d[k][j] < INF) // i->k, k->j should exist
                d[i][j] = min (d[i][j], d[i][k] + d[k][j]); // INF+INF won't happen
person Ralor    schedule 28.05.2014
comment
Использование min не позволяет вам поддерживать родительские указатели, такие как SequenceMatrix OP - person Gilthans; 29.05.2014

arrow_upward
0
arrow_downward

Исправлено !!! УРА

Не было никаких проблем с !!!!! узлы, где не сохраняются

A B C D в базе данных, а скорее A D B C, затем при чтении я работал над индексом, предполагая, что A находится в индексе 0, B находится в индексе 1 и так далее....

Извините за потраченное время и большое спасибо!!! за вашу помощь !!

person Oliver Ciappara    schedule 28.05.2014
comment
рад, что вы это поняли) сохранение некоторой атрибутивной информации в базе данных может помочь в таких случаях - person Ralor; 29.05.2014
comment
Важно отметить, что без приведенного ниже исправления Golden Dragon ваш код все равно не будет работать... Не забудьте принять его ответ. - person Gilthans; 29.05.2014
comment
на самом деле это не реализовано с исправлением Golden Dragon, и оно все еще работает, что меня немного смутило, почему, но все же большое спасибо всем за вклад, и именно так я добрался до проблемы, я посмотрел на данные в базе данных: ) - person Oliver Ciappara; 29.05.2014