Алгоритм носит имя двух американских учёных: Ричарда Беллмана (Richard Bellman) и Лестера Форда (Lester Ford). Форд фактически изобрёл этот алгоритм в 1956 г. при изучении другой математической задачи, подзадача которой свелась к поиску кратчайшего пути в графе, и Форд дал набросок решающего эту задачу алгоритма. Беллман в 1958 г. опубликовал статью, посвящённую конкретно задаче нахождения кратчайшего пути, и в этой статье он чётко сформулировал алгоритм в том виде, в котором он известен нам сейчас. Алгоритм Форда-Беллмана позволяет найти кратчайшие пути из одной вершины графа до всех остальных, даже для графов, в которых веса ребер могут быть отрицательными. Тем не менее, в графе не должно быть циклов отрицательного веса, достижимых из начальной вершины, иначе вопрос о кратчайших путях является бессмысленным. При этом алгоритм Форда-Беллмана позволяет определить наличие циклов отрицательного веса, достижимых из начальной вершины. Алгоритм использует динамическое программирование. Введем функцию динамического программирования: F[k][i] — длина кратчайшего пути из начальной вершины до вершины i, содержащего не более k ребер. Начальные значения зададим для случая k=0. В этом случае F[0] [start] = 0, а для всех остальных вершин i F[0][i] = INF. Далее будем вычислять значения функции F увеличивая число ребер в пути k, то есть вычислим кратчайшие пути, содержащие не более 1 ребра, кратчайшие пути, содержащие не более 2 ребер и т. д. Если в графе нет циклов отрицательного веса, то кратчайший путь между любыми двумя вершинами содержит не более ребра (- число вершин в графе), поэтому нужно вычислить значения F[n-1] [i], которые и будут длинами кратчайших путей от вершины start до вершины i). Целевая функция:
F[k][i]=min(F[k-1][i]+w(u,v))
1 Устанавливаются начальные значения расстояний от начальной вершины до всех остальных вершин графа. Расстояние до начальной вершины устанавливается равным 0, а расстояние до всех остальных вершин - бесконечности.
2 Проход по всем ребрам графа и обновление расстояний до вершин, если найден путь с меньшей стоимостью.
3 Пункт 2 повторяется для всех вершин графа |V|-1 раз, где |V| - количество вершин графа. Это позволяет учитывать пути с более чем одним ребром и обновлять оценки кратчайших путей.
4 Если после |V|-1 итераций происходит изменение расстояний, то это указывает на наличие отрицательного цикла в графе. В этом случае кратчайшие пути не могут быть определены, так как цикл может быть проходом с отрицательной суммой весов, и алгоритм продолжит обновлять расстояния бесконечно.
Асимптотическая оценка алгоритма Форда-Беллмана зависит от числа вершин в графе (|V|) и числа ребер (|E|). Общая сложность алгоритма составляет O (|V| * |E|), что делает его достаточно эффективным для небольших графов. Сравнение алгоритма с другими Алгоритм Форда-Беллмана является одним из классических алгоритмов для решения задачи нахождения кратчайшего пути во взвешенном графе. Однако есть еще алгоритмы, которые выполняют такие же функции, рассмотрим их различия и рассмотрим их асимптотику: Алгоритм Дейкстры: Алгоритм Дейкстры также используется для нахождения кратчайшего пути во взвешенном графе, но он применим только к графам с неотрицательными весами ребер и находит расстояние только до заданной вершины. В отличие от алгоритма Форда-Беллмана, алгоритм Дейкстры работает за время O (|E| + |V| log |V|), что делает его эффективнее для графов с положительными весами ребер. Алгоритм A*: Алгоритм A* является эвристическим алгоритмом поиска пути, который комбинирует информацию о стоимости достижения текущей вершины с эвристической оценкой стоимости достижения целевой вершины. Алгоритм A* обычно применяется в задачах поиска пути в графах, где требуется эффективно находить оптимальные пути. В отличие от алгоритма Форда-Беллмана, алгоритм A* может быть более эффективным, если имеется эвристическая функция, которая хорошо приближает оценку расстояния до цели. Алгоритм Беллмана-Форда с очередью с приоритетами: это оптимизированная версия алгоритма Форда-Беллмана, которая использует очередь с приоритетами для выбора вершин с наименьшей оценкой расстояния. Эта оптимизация позволяет сократить количество повторных просмотров вершин и сделать алгоритм более эффективным. Сравнение этих алгоритмов зависит от особенностей конкретной задачи и свойств графа. Алгоритм Форда-Беллмана является универсальным и применимым к графам с отрицательными весами ребер, в то время как другие алгоритмы имеют свои ограничения и предположения о графе. Если в графе нет отрицательных циклов, то алгоритм Форда-Беллмана может быть предпочтительным выбором, особенно когда важна общая применимость и гибкость алгоритма. Однако, если граф имеет специфические свойства или ограничения, другие алгоритмы могут быть более эффективными или предоставлять дополнительные возможности, такие как использование эвристической информации или ограничений на веса ребер.
В заключение, алгоритм Форда-Беллмана является важным и мощным инструментом для решения задачи нахождения кратчайшего пути во взвешенном графе. Он обладает рядом преимуществ, таких как универсальность, способность работать с графами с отрицательными весами ребер и простота реализации. В ходе выполнения курсовой работы была проведена тщательная аналитическая и практическая работа по изучению и реализации алгоритма Форда-Беллмана. Были изучены его основные принципы, математическая модель и время работы. Также был проведен анализ и сравнение алгоритма с другими алгоритмами для нахождения кратчайшего пути. В итоге алгоритм Форда-Беллмана является мощным инструментом, который позволяет эффективно определить кратчайшее время пути груза от заказчика до склада. Его простата и гибкость делают его незаменимым инструментом для решения широкого спектра задач в различных областях.