4446
правок
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
Строка 80: | Строка 80: | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Клейн [8] предложил технику, улучшающую время построения плотного графа расстояний до O( | Клейн [8] предложил технику, улучшающую время построения плотного графа расстояний до <math>O(n \; log^2 \; n)</math> для случая неотрицательных весов ребер; она также снижает амортизированное время выполнения для динамического случая до <math>O(n^{2/3} \; log^{5/3} \; n)</math>. Также для планарного графа с неотрицательными весами ребер Кабелло [1] приводит более быстрый алгоритм вычисления кратчайших расстояний между k парами вершин. Однако задача улучшения временной границы <math>O(n \; log^3 \; n)</math> алгоритма нахождения кратчайших путей в планарных графах с весами ребер общего вида все еще остается нерешенной. | ||
Неизвестно, как обрабатывать вставку и удаление ребер в динамической структуре данных. Возможно, потребуется введение новой структуры данных вместо плотного графа расстояний, поскольку последний определяется посредством декомпозиции. | Неизвестно, как обрабатывать вставку и удаление ребер в динамической структуре данных. Возможно, потребуется введение новой структуры данных вместо плотного графа расстояний, поскольку последний определяется посредством декомпозиции. | ||
== См. также == | == См. также == |
правок