Алгоритм поиска кратчайших путей с единственным источником: различия между версиями

Торупу удалось избежать «бутылочного горлышка» сортировки, присущего алгоритму Дейкстры, за счет предварительного вычисления ''иерархии компонентов'' за линейное время. Алгоритм из [17] действует подобно алгоритму Дейкстры [4], но использует иерархию компонентов для определения групп вершин, которые могут быть посещены в любом порядке. В более поздней работе [18] Торуп расширил алгоритм таким образом, чтобы он мог работать с длинами ребер, представляющими собой числа с плавающей точкой. (''Определение кратчайшего пути обладает определенной гибкостью, поскольку сложение с плавающей точкой не является ни коммутативным, ни ассоциативным'')).

* [[Алгоритм поиска кратчайших путей при помощи матричного произведения]]