Курсовая работа: Разработка и реализация алгоритма Флойда и Беллмана-Форда для поиска кратчайшего пути между всеми вершинами графа

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

Алгоритм Флойда, или алгоритм Флойда-Уоршелла, эффективен для нахождения кратчайших путей между всеми парами вершин в графе, обеспечивая при этом полное представление о связности между ними. Он основан на динамическом программировании и имеет временную сложность O(n^3), что делает его приемлемым для относительно небольших графов. Этапы алгоритма включают инициализацию матрицы расстояний, последующую её итеративную корректировку с учётом промежуточных вершин, что в итоге позволяет получить оптимальные пути для каждой пары вершин.

Алгоритм Беллмана-Форда, в свою очередь, предназначен для работы с графами, где могут присутствовать отрицательные веса рёбер. Его эффективность заключается в способности корректировать расстояния до всех вершин за O(V * E), где V — количество вершин, а E — количество рёбер. Процесс включает пошаговое обновление расстояний, что обеспечивает необходимую гибкость при обнаружении цикла отрицательного веса.

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