Алгоритм Беллмана-Форда онлайн

Алгоритм Беллмана-Форда для графа: введите направленные ребра с весами, получите кратчайшие расстояния, путь до цели и проверку отрицательного цикла.

Направленные ребра с весами

Вершины и маршрут

Все вершины, если есть изолированные Стартовая вершина Целевая вершина

Формат строки: A B -4, где ребро идет из A в B. Алгоритм Беллмана-Форда допускает отрицательные веса и проверяет достижимый отрицательный цикл.

Расстояние до цели-

Достижимые вершины-

Отрицательный цикл-

Для новичка: как читать расчет

1. Старт Расстояние до стартовой вершины равно 0, остальные сначала считаются недостижимыми.

2. Релаксации Алгоритм несколько раз пробует улучшить расстояния по всем ребрам.

3. Путь Если цель достижима, калькулятор восстанавливает маршрут по предыдущим вершинам.

4. Цикл Если после основных проходов расстояние еще улучшается, есть достижимый отрицательный цикл.

Передача файла

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

Открыть страницу

Что решает алгоритм Беллмана-Форда

Алгоритм Беллмана-Форда ищет кратчайшие пути от выбранной стартовой вершины до остальных вершин в направленном взвешенном графе. В отличие от Дейкстры, он допускает отрицательные веса ребер.

Формат ввода

Каждое ребро пишите с новой строки: A B -4. Это означает направленное ребро из A в B с весом -4. Для изолированных вершин заполните отдельное поле со списком вершин.

Как читать результат

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

Что решает алгоритм Беллмана-Форда

Формат ввода

Как читать результат

Связанные калькуляторы