10. Как найти кратчайшее расстояние в графе?

Нахождение кратчайшего расстояния в графе:

Кратчайшее расстояние между двумя вершинами — это путь с минимальной суммой весов рёбер, соединяющий эти вершины.

Основные алгоритмы:

• Алгоритм Дейкстры: находит кратчайшие пути от одной начальной вершины до всех остальных вершин в графе с неотрицательными весами рёбер.
• Алгоритм Беллмана-Форда: находит кратчайшие пути от одной начальной вершины до всех остальных в графе, который может содержать рёбра с отрицательными весами (но без отрицательных циклов).
• Алгоритм Флойда-Уоршелла: находит кратчайшие пути между всеми парами вершин в графе.