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

Интерактивное сравнение: https://grundyjs.ru/algorithms/shortest-path-comparison/?utm_source=rutube&utm_medium=social&utm_campaign=shortest_path_comparison&utm_content=horizontal На одном ориентированном графе сравниваем три алгоритма. Дейкстра закрепляет вершину с наименьшей известной стоимостью от старта и требует неотрицательных весов. Беллман — Форд повторяет полные проходы по рёбрам; он допускает отрицательные веса. Оба вычисляют расстояния от одного источника. Флойд — Уоршелл разрешает промежуточные вершины по очереди и вычисляет матрицу расстояний между всеми парами. Для сравнения берём её строку A. На исходных весах все три находят путь A → B → C → D: 3 + 2 + 2 = 7. После изменения B → C на −2 стоимость становится 3. Дейкстру в этом режиме не запускаем; Беллман — Форд и Флойд — Уоршелл продолжают работать. Добавляем C → B веса 1: цикл B → C → B стоит −1. Повторяя его, можно удешевлять путь из A в D сколько угодно — конечного минимума нет (−∞). Но D → D остаётся 0: от D этот цикл недостижим. Обратного пути D → A нет (∞). При единичных весах минимальная стоимость совпадает с минимальным числом рёбер: прямое ребро A → D даёт стоимость 1. Такты анимации показывают этапы алгоритмов, а не замер быстродействия. В интерактивном примере можно менять веса, источник и цель, сравнивать этапы и поделиться ссылкой на свой граф. Авторская озвучка, без музыки. Русские субтитры подготовлены отдельной дорожкой. #алгоритмы #Дейкстра #БеллманФорд #ФлойдУоршелл #графы #программирование