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

Принцип работы: на каждом шаге помечается определённым образом выбранная вершина, а далее просматриваются все последующие (ещё не отмеченные) вершины графа и вычисляется длина пути до каждой из них от начальной точки. 2

Некоторые шаги алгоритма Дейкстры:

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

Алгоритм Дейкстры используется в ряде реальных приложений, например для маршрутизации сетевых пакетов. 3