Алгоритм Дейкстры
Классический алгоритм поиска кратчайших путей от одной вершины до всех остальных в графе с неотрицательными весами рёбер — Эдсгер Дейкстра, 1956 год, опубликован в 1959-м.
Идея: взять вершину с наименьшим известным расстоянием, обновить расстояния до её соседей, повторить. С двоичной кучей в роли очереди с приоритетом — O((V+E) log V). С кучей Фибоначчи — O(E + V log V): теоретически быстрее, на практике редко.
На нём держится маршрутизация в GPS, BGP/OSPF, обход социальных графов, призраки в Pac-Man. Конкуренты: A* (с эвристикой, быстрее для одной пары вершин), Беллман — Форд (отрицательные веса), Флойд — Уоршелл (все пары).