Для решения задачи о кратчайшем пути в графе можно использовать алгоритм Дейкстры. 14 Он находит кратчайший путь от одной из вершин графа до всех остальных. 2

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

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

Алгоритм Дейкстры работает только для графов без рёбер отрицательного веса. 4