Исследование алгоритмов поиска кратчайшего пути в неориентированных графах

Печик Ирина Юрьевна, ФКН ПИ 2 курс

Цель работы:

Экспериментальное исследование алгоритмов поиска кратчайшего пути в неориентированном графе

Рассматриваемые алгоритмы

• Алгоритм Дейкстры
• Алгоритм Флойда-Уоршела
• Алгоритм Форда-Беллмана
• Алгоритм Левита

Сгенерированные тестовые данные:

• Полные графы с числом вершин от 10 до 1010 (шаг 50)
• Связные графы с числом вершин от 10 до 1010 (шаг 50) и коэффициентом плотности приблизительно 0.4-0.5
• Разреженные графы (деревья) с числом вершин от 10 до 1010 (шаг 50)

Выходные сравнительные графики

• Графики зависимости отдельно по каждому алгоритму:
  • Времени работы от числа вершин
  • Времени работы от числа ребер
• Агрегированные графики зависимости:
  • Времени работы от числа вершин
  • Времени работы от числа ребер

Усреднение результатов замеров проводится большим количеством тестирований