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