Алгоритмы и структуры данных. Лекция 13

Пути в графах.

• Расстояния в графе.
• Поиск в ширину: обход, дерево кратчайших путей, сравнение с поиском в глубину.
• Алгоритм Дейкстры: адаптация поиска в ширину введением дополнительных вершин; установка будильников; алгоритм Дейкстры; альтернативный взгляд на алгоритм: последовательное расширение множества вершин, до которых расстояние уже посчитано; время работы алгоритма при различных реализациях очереди с приоритетами.