forward star

Алгоритм Дейкстры находит кратчайшие пути от одной вершины до всех остальных во взвешенном графе с неотрицательными рёбрами. Наивная реализация с линейным поиском минимума работает за O(n² + m), что приемлемо для плотных графов. Для разреженных графов, где m значительно меньше n², бинарная куча...