Калькулятор кратчайшего пути в графе

Задача о кратчайшем пути

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

Алгоритм Дейкстры

Каждой вершине приписывается метка — длина лучшего найденного пути до неё. У начальной вершины метка 0, у остальных — бесконечность. На каждом шаге выбирается непосещённая вершина с наименьшей меткой; её метка становится окончательной, а метки соседей уменьшаются, если путь через выбранную вершину короче:

d(v) = min(d(v), d(u) + w(u, v))

Алгоритм заканчивается, когда все достижимые вершины посещены. Чтобы восстановить путь, для каждой вершины запоминается предыдущая. Время работы простой реализации — O(n²), с двоичной кучей — O(m log n). Алгоритм Дейкстры верен только для неотрицательных весов: окончательная метка может оказаться неверной, если позже найдётся ребро с отрицательным весом.

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

Беллман — Форд n − 1 раз проходит по всем рёбрам и выполняет ту же релаксацию d(v) = min(d(v), d(u) + w(u, v)). Он работает и с отрицательными весами, а время работы — O(n · m). Если после n − 1 проходов какую-то метку ещё можно уменьшить, в графе есть цикл отрицательного веса: обходя его снова и снова, можно сделать путь сколь угодно коротким, и кратчайшего пути до вершин, достижимых из цикла, не существует. Калькулятор находит и показывает такой цикл.

В неориентированном графе ребро с отрицательным весом само образует отрицательный цикл: по нему можно ходить туда и обратно. Поэтому отрицательные веса имеют смысл только в ориентированных графах.

Алгоритм Флойда — Уоршелла

Чтобы найти расстояния сразу между всеми парами вершин, удобен алгоритм Флойда — Уоршелла. Вершины по очереди разрешается использовать как промежуточные: d(i, j) = min(d(i, j), d(i, k) + d(k, j)) для k = 1…n. Три вложенных цикла дают время O(n³). Калькулятор выводит итоговую матрицу для графов до 20 вершин.

Пример

В графе из примера ищем путь из вершины 1 в вершину 5. Сначала метки соседей 1: d(2) = 7, d(3) = 9, d(6) = 14. Наименьшая метка у вершины 2, через неё d(4) = 7 + 15 = 22. Затем выбирается вершина 3: d(4) = min(22, 9 + 11) = 20, d(6) = min(14, 9 + 2) = 11. Из вершины 6 получаем d(5) = 11 + 9 = 20. Ответ: длина 20, путь 1 → 3 → 6 → 5. Прямое ребро 1–6 длиной 14 оказалось хуже обхода через вершину 3.

Как задать граф

В списке рёбер каждая строка содержит начало, конец и вес: «A B 5». Имена вершин — любые слова или числа. В матрице весов строка i описывает рёбра из вершины i; ноль или прочерк означает, что ребра нет. Для неориентированного графа матрица должна быть симметричной. При переключении формата введённый граф переводится автоматически.