Лабораторная работа №25. Понятие графа. Алгоритмы поиска кратчайших путей

Рис. 4. Демонстрация волнового алгоритма
Заметим, что перебор методом поиска в ширину по сравнению с перебором с возвратом, как правило, требует больше вспомогательной памяти, которая необходима для хранения информации, чтобы построить путь при обратном ходе и пометить посещенные вершины. Однако он работает быстрее, так как совершенно исключается посещение одной и той же клетки более чем один раз.

Ключевые термины

Алгоритм Дейкстры – это алгоритм нахождения кратчайшего пути от одной из вершин графа до всех остальных, который работает только для графов без ребер отрицательного веса.
Алгоритм Флойда – это алгоритм поиска кратчайшего пути между любыми двумя вершинами графа.
Волновой алгоритм – это переборный алгоритм, который основан на поиске в ширину и состоит из двух этапов: распространение волны и обратный ход.
Кратчайший путь – это путь в графе, то есть последовательность вершин и ребер, инцидентных двум соседним вершинам, и его длина.
Переборный алгоритм – это алгоритм обхода графа, основанный на последовательном переборе возможных путей.

Краткие итоги

1. 
   Нахождение кратчайшего пути на сегодняшний день является актуальной задачей
   
2. 
   К наиболее эффективным алгоритмам нахождения кратчайшего пути в графах относятся алгоритм Дейкстры, алгоритм Флойда и переборные алгоритмы. Эти алгоритмы эффективны при достаточно небольших количествах вершин.
   
3. 
   В реализации алгоритма Дейкстры строится множество вершин, для которых кратчайшие пути от начальной вершины уже известны. Следующие шаги основаны на добавлении к имеющемуся множеству по одной вершине с сохранением длин оптимальных путей.
   
4. 
   Сложность алгоритма Дейкстры зависит от способа нахождения вершины, а также способа хранения множества непосещенных вершин и способа обновления длин.
   
5. 
   Метод Флойда основывается на факте, что в графе с положительными весами ребер всякий неэлементарный кратчайший путь состоит из других кратчайших путей.
   
6. 
   Если граф представлен матрицей смежности, то время выполнения алгоритма Флойда имеет порядок O(n³).
   
7. 
   Переборные алгоритмы являются алгоритмами поиска оптимального решения.
   
8. 
   Волновой алгоритм является переборным алгоритмом, который основан на поиске в ширину и состоит из двух этапов: распространение волны и обратный ход.
   
9. 
   Перебор методом поиска в ширину, по сравнению с перебором с возвратом, требует больше вспомогательной памяти для хранения информации, однако, он работает быстрее, так как исключается посещение одной и той же вершины более чем один раз.