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