Кратчайший маршрут: установка меток, коррекция меток, другие задачи поиска кратчайшего маршрута, алгоритм Флойда, применения метода поиск

1. Графы являются моделью представления данных, основанных на отношениях между элементами множеств.
2. Для представления графов используется несколько способов: список ребер, матрица смежности, матрица инцидентности.
3. Для организации поиска на графах используются обходы в глубину и в ширину.
4. Реализацию обходов можно осуществлять рекурсивными и нерекурсивными алгоритмами.
5. От вида графа и способа его представления зависит временная сложность выполнения алгоритма.

Введение………………………………………………………………………... 3
1 Алгоритмы обхода графа……………………………………………………. 5
1.1 Поиск в глубину…………………………………………………….. 6
1.2 Поиск в ширину……………………………………………………... 7
2 Алгоритмы нахождения кратчайшего пути………………………………... 9
2.1 Алгоритм Дейкстры………………………………………………… 10
2.2 Алгоритм Флойда…………………………………………………… 12
2.3 Переборные алгоритмы…………………………………………….. 15
Заключение…………………………………………………………………….. 20