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