Переставляет ли внешний цикл в алгоритме Флойда-Уоршалла, поскольку большинство внутренних циклов меняют алгоритм

Следующий код предназначен для алгоритма Флойда-Уоршалла.

for (int k = 0; k < n; ++k) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]); 
        }
    }
}

Предлагаю переписать код следующим образом

for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
        for (int k = 0; k < n; ++k) {
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]); 
        }
    }
}

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


algorithm shortest-path floyd-warshall
person Andy Lee    schedule 04.12.2020    source источник
comment
Вы запускали какой-нибудь тест?   -  person MrSmith42    schedule 04.12.2020

Ответы (2)


arrow_upward
5
arrow_downward

Нет, это вообще не сработает. В основе алгоритма Флойда – Уоршалла лежит идея найти кратчайшие пути, которые проходят через меньшее подмножество узлов: 1..k, и затем увеличить размер этого подмножества.

Важно, чтобы расстояние между парами узлов было адаптировано к подмножеству 1..k, прежде чем увеличивать размер этого подмножества.

В качестве примера возьмем пример графика, использованного в Википедии:

введите описание изображения здесь

Давайте сосредоточимся на пути, который существует от узла 3 к узлу 1, который имеет путь наименьшего веса 2 + -1 + 4 = 5.

Давайте запустим исходный алгоритм и ваш вариант, чтобы узнать, определяет ли он это расстояние:

Оригинальный (правильный) алгоритм

let d = [
    [0, Infinity, -2, Infinity],
    [4, 0, 3, Infinity],
    [Infinity, Infinity, 0, 2],
    [Infinity, -1, Infinity, 0]
];
let n = d.length;

for (let k = 0; k < n; ++k) {
    for (let i = 0; i < n; ++i) {
        for (let j = 0; j < n; ++j) {
            d[i][j] = Math.min(d[i][j], d[i][k] + d[k][j]); 
        }
    }
}

console.log("distance from 3 to 1 = ", d[2][0]);  // 5 -- correct

Ваш предлагаемый алгоритм

let d = [
    [0, Infinity, -2, Infinity],
    [4, 0, 3, Infinity],
    [Infinity, Infinity, 0, 2],
    [Infinity, -1, Infinity, 0]
];
let n = d.length;

for (let i = 0; i < n; ++i) {
    for (let j = 0; j < n; ++j) {
        for (let k = 0; k < n; ++k) {
            d[i][j] = Math.min(d[i][j], d[i][k] + d[k][j]); 
        }
    }
}

console.log("distance from 3 to 1 = ", d[2][0]);  // Infinity -- wrong

person trincot    schedule 04.12.2020

arrow_upward
0
arrow_downward

Если вы превратите внешний цикл во внутренний, вы получите матричное умножение над тропическим полукольцом (то есть с min как сложение и суммой как умножение) вместо Флойда Уоршалла.

Он вычислит путь с наименьшим весом, содержащий не более двух шагов. Вы можете возвести матрицу в степень, повторяя возведение в квадрат, чтобы получить тот же результат, что и Флойд Уоршалл, конечно (со сложностью O (V ^ 3 log (V)), и он будет лучше обрабатывать циклы с отрицательным весом

person saolof    schedule 08.03.2021