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