Алгоритм Торупа для поиска кратчайшего расстояния во взвешенном графе за линейное время (Филипп Грибов)

Семинар по алгоритмам и структурам данных ФКН Для задачи поиска кратчайшего пути в графе давно известен алгоритм Дейкстры, который при использовании фибоначчиевой кучи работает за асимптотику 𝓞(|E| |V| log |V|). К сожалению, алгоритм Дейкстры нельзя ускорить до линейного времени работы, так как это потребовало бы существования кучи с линейным временем работы. На семинаре рассматривается алгоритм Торупа, который позволяет искать кратчайшее расстояние в графе за время 𝓞(|V| |E|) с дополнительным ограничением, что веса ребер являются целыми числами. Данный алгоритм использует отличный от алгоритма Дейкстры подход к поиску кратчайшего расстояния в графе. В процессе алгоритма граф будет разделяться на особое дерево компонент и вершины будут рассматриваться в порядке, никак не связанном с длиной кратчайшего пути до них. В самом алгоритме Торупа используется множество других достаточно сложных алгоритмов, таких как линейный алгоритм построения остовного дерева, линейный СНМ при особых условиях запросов, atomic heap. Мы обзорно пройдемся по основным шагам алгоритма Торупа, тем самым сведя поиск кратчайшего пути к набору задач, которые в науке хорошо изучены и для которых существуют оптимальные решения. Выступает Филипп Грибов, преподаватель департамента больших данных и информационного поиска ФКН ВШЭ. 19 ноября 2024 Семинар по алгоритмам и структурам данных ФКН: ФКН: ​​