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

Принцип работы алгоритма Дейкстры: 2

1. Всем вершинам, за исключением первой, присваивается вес равный бесконечности, а первой вершине — 0. 2
2. Все вершины не посещены. 2
3. Первая вершина объявляется текущей. 2
4. Вес всех невыделенных вершин пересчитывается по формуле: вес невыделенной вершины есть минимальное число из старого веса данной вершины, суммы веса текущей вершины и веса ребра, соединяющего текущую вершину с невыделенной. 2
5. Среди невыделенных вершин ищется вершина с минимальным весом. 2 Если такая не найдена, то есть вес всех вершин равен бесконечности, то маршрута не существует. 2 Иначе, текущей становится найденная вершина, она же выделяется. 2
6. Если текущей вершиной оказывается конечная, то путь найден, и его вес есть вес конечной вершины. 2
7. Переход на шаг 4. 2

Результат алгоритма — список кратчайших маршрутов до каждой точки из исходной, для каждого маршрута указана его длина. 1