Дейкстра, Беллман — Форд и Флойд — Уоршелл: сравнение

Один граф — разные вопросы

Все рёбра ориентированы и имеют одинаковый вес во всех трёх моделях. Дейкстра и Беллман — Форд вычисляют расстояния от выбранного источника ко всем достижимым вершинам. В отличие от отдельного примера Дейкстры, сравнение продолжает поиск после закрепления выбранной цели. Другая цель выбирает другой ответ в строке источника.

Флойд — Уоршелл вычисляет целую матрицу независимо от выбранной пары. Повторённая строка в его панели — строка выбранного источника: её можно напрямую сопоставить с результатами двух других алгоритмов. Полная матрица остаётся видимой. Выберите D → A и проверьте, почему направление ребра важно.

Каждая вершина обозначает один и тот же объект во всех панелях. Цвета различают алгоритмы: синий — Дейкстра, жёлтый — Беллман — Форд, фиолетовый — Флойд — Уоршелл. Цветные линии на графе показывают текущие восстанавливаемые маршруты для выбранной пары, кольца — вершины завершённого этапа. В списке подсветки можно оставить один алгоритм.

Что означает один такт анимации

Дейкстра закрепляет вершины в порядке минимального известного расстояния. Вершины, закреплённые на одном расстоянии, объединены в один визуальный этап, в том числе открытые через нулевые рёбра. Минимум здесь ищется линейным просмотром границы, без двоичной кучи. Закреплённые вершины эта реализация повторно не открывает.

Беллман — Форд на каждом проходе проверяет весь список рёбер. Релаксация заменяет d(v), если d(u) + w(u,v) меньше. Реализация меняет расстояния на месте: улучшение может использоваться дальше в том же проходе. Плеер показывает законченный проход целиком, затем контрольную проверку и итоговую классификацию затронутых вершин. Проход без улучшений завершает работу досрочно.

Флойд — Уоршелл разрешает ещё одну промежуточную вершину k и проверяет d(i,j) = min(d(i,j), d(i,k) + d(k,j)) для всех пар. Обновления одного этапа читают одну и ту же прежнюю матрицу и появляются вместе. Заключительные этапы проверяют диагональ и отмечают пары, затронутые отрицательными циклами.

За такт каждый ещё работающий алгоритм проходит один свой этап. Объём работы в этих этапах разный. Длительность анимации, число тактов и счётчики проверок рёбер или пар не являются замером производительности. Завершившаяся панель сохраняет результат, пока остальные продолжают работу.

Дейкстра считает просмотренные исходящие рёбра закрепляемых вершин. Беллман — Форд считает проверки рёбер в проходах релаксации и контрольном проходе; распространение отметок затронутых вершин в этот счётчик не входит. Флойд — Уоршелл считает V² проверок пар на каждую промежуточную вершину, включая недостижимые пары. Это разные виды операций.

Неотрицательные веса: 10 → 9 → 7

Прямое ребро A → D стоит 10. Путь A → B → D стоит 3 + 6 = 9. Маршрут A → B → C → D стоит 3 + 2 + 2 = 7. Все три алгоритма возвращают 7 для A → D. Промежуточные оценки различаются, потому что улучшения распространяются в разном порядке.

Для Беллмана — Форда порядок рёбер намеренно развёрнут. Первый проход находит B = 3 и D = 10, следующий — C = 5 и D = 9, третий улучшает D до 7. Дейкстра закрепляет A, B, C, D. Флойд — Уоршелл сначала улучшает A → D через B, затем через C.

При единичных весах минимальная стоимость совпадает с минимальным количеством рёбер. В этом графе прямое A → D тогда стоит 1 и выгоднее трёх переходов. В общем случае равные по цене пути могут различаться: пример сохраняет первый строго лучший маршрут и не минимизирует число рёбер среди равных по стоимости вариантов.

Отрицательное ребро меняет применимость

Замените вес B → C на −2 или выберите пример с отрицательным ребром. Отрицательного цикла всё ещё нет. Беллман — Форд и Флойд — Уоршелл находят A → B → C → D стоимостью 3 + (−2) + 2 = 3.

Дейкстра не запускается и не показывает предположительный ответ. Отрицательное ребро может позже улучшить уже закреплённую вершину и нарушить правило этой реализации. Проверка отклоняет отрицательное ребро в любой части графа, включая отдельную компоненту. Это явный контракт примера; он не означает, что каждый граф с отрицательным ребром обязательно дал бы неправильное число.

Контрпример: A → B = 1, A → C = 2, C → B = −3. Если закрепить B со стоимостью 1 до посещения C и больше не открывать её, улучшение до −1 будет пропущено. Случайно правильный ответ на другом графе с отрицательным ребром не доказывает гарантию алгоритма.

Отрицательный цикл отменяет не все ответы

Добавим C → B = 1. Цикл B → C → B стоит −2 + 1 = −1. Из A в него можно войти, а затем попасть в D, поэтому для A → D конечного минимума нет. Беллман — Форд отмечает затронутые цели от A; Флойд — Уоршелл — каждую пару, чей маршрут может пройти через такой цикл. Оба показывают −∞ для A → D. Конечные промежуточные числа до классификации — ещё не ответы о кратчайших путях.

Выберите D → D на этом графе. Из D цикл недостижим, поэтому остаться на месте по-прежнему стоит ноль. D → A остаётся недостижимой парой (∞). Цикл делает пару неограниченной только тогда, когда источник может дойти до цикла, а из цикла можно дойти до цели.

Пример с отдельным циклом добавляет E с отрицательной петлёй. Из A Беллман — Форд по-прежнему находит A → D = 3 и не видит этот цикл. Флойд — Уоршелл показывает E → E = −∞ в полной матрице, сохраняя A → D = 3. Если выбрать источником E, цикл обнаружит и Беллман — Форд. Дейкстра остаётся недоступной из-за требования неотрицательных весов во всём графе.

Объём работы, память и выбор алгоритма

V — число вершин, E — число направленных рёбер. Таблица описывает реализации этого плеера. У Дейкстры минимум ищется линейным просмотром границы: O(V² + E). Для варианта с двоичной кучей обычно указывают O((V + E) log V). Дейкстра и Беллман — Форд хранят копию графа и линейные массивы источника, используя O(V + E) рабочей памяти. Их выходная строка занимает O(V).

Беллман — Форд требует O(VE + V) времени в худшем случае с учётом инициализации и распространения отметок от улучшаемых рёбер. Для непустых графов обычно пишут O(VE). Флойд — Уоршелл требует O(V³) времени и O(V²) рабочей памяти, включая матрицы следующих шагов и достижимости. Его выход — полная матрица размера O(V²).

Снимки анимации — дополнительная память сверх этих оценок. Сохранённые матричные этапы занимают O(V³); подробная временная история Беллмана — Форда при подготовке может занимать O(V²E). Интерактивный ввод ограничен шестью вершинами, не более чем 32 уникальными направленными парами и целыми весами от −99 до 99. Неверная правка или повреждённая ссылка сохраняет текущий корректный проход.

Для одного источника с неотрицательными весами начните с Дейкстры. При отрицательных рёбрах Беллман — Форд даёт расстояния от источника и классификацию достижимых циклов. Если на небольшом графе нужны многие запросы между разными парами, рассмотрите Флойда — Уоршелла. Один запуск алгоритма от источника не равен по объёму задаче вычисления всех пар.

Как сравнение использует готовые модели

Плеер не заменяет три алгоритма отдельной имитацией. Код ниже вызывает те же проверенные модели, что и отдельные статьи. Дейкстра запускается с направленными рёбрами и вычислением всей строки источника; строка Беллмана — Форда сопоставляется с соответствующей строкой матрицы. null означает невыполненное условие применимости Дейкстры. Импорты относятся к модулям data этого сайта.

Сравнение объединяет настоящие снимки в законченные визуальные этапы. Ссылка сохраняет граф, источник, цель, подсветку, такт на паузе и скорость на чистой странице плеера. Сохранение видео записывает те же состояния с начала с выбранной скоростью и подсветкой, без озвучки и музыки.

import { createFloydInput, floydWarshallSteps } from "./floyd-warshall";
import { dijkstraSteps } from "./dijkstra";
import { bellmanFordSteps } from "./bellman-ford";

function compareShortestPaths(graph, start, target) {
  const input = createFloydInput({ graph, start, target });
  const dijkstra = graph.edges.every(e => e.weight >= 0)
    ? dijkstraSteps(graph, start, target, {
        directed: true, allTargets: true
      }).at(-1).state.distance
    : null;
  const bellmanFord = bellmanFordSteps(input).at(-1).state.distance;
  const floydWarshall = floydWarshallSteps(input).at(-1).state.distance;
  return {
    dijkstra,
    bellmanFord,
    floydWarshall,
    selected: {
      dijkstra: dijkstra?.[target] ?? null,
      bellmanFord: bellmanFord[target],
      floydWarshall: floydWarshall[start][target]
    }
  };
}