Как работает Floyd-Warshall Algorthm и что такое K? - PullRequest
Новая
       71

Как работает Floyd-Warshall Algorthm и что такое K?

2 голосов
/ 23 ноября 2011

Мне трудно понять Алгоритм Флойда-Варшалла .Я знаю, как это работает, как я знаю, как это сделать вручную, но мне нужно понять это через проницательный компьютер. 

FOR k <-- 1 TO N DO
    FOR i <-- 1 TO N DO
        FOR j <-- TO N DO 
            IF Djk + Dkj < DiJ THEN
                Dij <-- djk + dkj

k, i и j - переменные для итерациии он повторяется до значения n, и я думаю, что это вложенный цикл, а затем он смотрит на каждый узел меньше, чем находит кратчайший путь?

Ответы [ 2 ]

4 голосов
/ 23 ноября 2011

Чрезвычайно упрощенное значение k во Флойд-Варшалле является «путевой точкой» на графе.Последние две строки можно интерпретировать следующим образом: «Если вы можете добраться от i до k, а затем от k до j быстрее, чем от i до j, по любому пути, который вы до сих пор нашли, то путь от i до j через k становитсяНовый кратчайший путь ".

1 голос
/ 02 июня 2014

K представляет промежуточную вершину.Итак, внешний цикл в основном говорит, что пусть K-я вершина будет промежуточной точкой остановки.Затем внутренние два цикла проверяют каждый элемент в матрице смежности и проверяют, меньше ли расстояние с использованием K (используя K в качестве промежуточной вершины), чем расстояние от вершины i до j (число в позиции i, j в смежности).матрица).Если расстояние меньше, обновите d [i, j].

...