4446
правок
Поиск кратчайших путей в планарных графах с отрицательными весами ребер: различия между версиями
Материал из WEGA
Поиск кратчайших путей в планарных графах с отрицательными весами ребер (посмотреть исходный код)
Версия от 14:08, 1 октября 2023
, 1 октября 2023нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
| (не показано 9 промежуточных версий этого же участника) | |||
| Строка 1: | Строка 1: | ||
== Ключевые слова и синонимы == | == Ключевые слова и синонимы == | ||
Поиск кратчайших путей в планарных графах с весами дуг общего вида; поиск кратчайших путей в планарных графах с произвольными весами дуг | Поиск кратчайших путей в планарных графах с весами дуг общего вида; поиск кратчайших путей в планарных графах с произвольными весами дуг | ||
== Постановка задачи == | == Постановка задачи == | ||
| Строка 10: | Строка 9: | ||
== Нотация == | == Нотация == | ||
Пусть даны ориентированный граф G = (V, E) и весовая функция <math>w: E \to \mathbb{R} \;</math> на его ориентированных ребрах. Маркировка расстояния для вершины-источника s представляет собой функцию <math>d: V \to \mathbb{R} \;</math>, такую, что d(v) имеет минимальную длину среди всех путей из s в v, где [[длина пути]] P определена как <math>\sum_{e \in P} w(e) \;</math>. | Пусть даны ориентированный граф G = (V, E) и весовая функция <math>w: E \to \mathbb{R} \;</math> на его ориентированных ребрах. ''Маркировка расстояния'' для вершины-источника s представляет собой функцию <math>d: V \to \mathbb{R} \;</math>, такую, что d(v) имеет минимальную длину среди всех путей из s в v, где [[длина пути]] P определена как <math>\sum_{e \in P} w(e) \;</math>. | ||
| Строка 17: | Строка 16: | ||
Дано: ориентированный граф G = (V, E), весовая функция <math>w: E \to \mathbb{R} \;</math>, вершина-источник <math>s \in V \;</math>. | Дано: ориентированный граф G = (V, E), весовая функция <math>w: E \to \mathbb{R} \;</math>, вершина-источник <math>s \in V \;</math>. | ||
Требуется: если граф G не содержит циклов отрицательной длины, вывести маркировку расстояния d для | Требуется: если граф G не содержит циклов отрицательной длины, вывести маркировку расстояния d для вершины-источника s. В противном случае выдать сообщение, что в графе имеется цикл отрицательной длины. | ||
| Строка 28: | Строка 27: | ||
Алгоритм выполняет рекурсивную декомпозицию: на каждом уровне фрагмент с n вершинами и r граничными вершинами разделяется на два подфрагмента, таких, что каждый подфрагмент содержит не более <math>2n/3 \;</math> вершин и не более <math>2r/3 + c \sqrt{n} \;</math> граничных вершин при некотором константном значении c. В данном рекурсивном контексте граничной вершиной подфрагмента считается любая граничная вершина исходного фрагмента и любая новая граничная вершина, порожденная декомпозицией фрагмента. | Алгоритм выполняет ''рекурсивную декомпозицию'': на каждом уровне фрагмент с n вершинами и r граничными вершинами разделяется на два подфрагмента, таких, что каждый подфрагмент содержит не более <math>2n/3 \;</math> вершин и не более <math>2r/3 + c \sqrt{n} \;</math> граничных вершин при некотором константном значении c. В данном рекурсивном контексте граничной вершиной подфрагмента считается любая граничная вершина исходного фрагмента и любая новая граничная вершина, порожденная декомпозицией фрагмента. | ||
Уровень декомпозиции в рамках этого процесса может быть определен естественным образом. Исходный граф в целостном виде имеет 0 уровень декомпозиции, фрагменты первой декомпозиции исходного графа – 1 уровень, и так далее. | ''Уровень декомпозиции'' в рамках этого процесса может быть определен естественным образом. Исходный граф в целостном виде имеет 0 уровень декомпозиции, фрагменты первой декомпозиции исходного графа – 1 уровень, и так далее. | ||
Для каждого фрагмента декомпозиции рекурсивно вычисляются расстояния по кратчайшим путям между всеми | |||
Для каждого фрагмента декомпозиции рекурсивно вычисляются расстояния по кратчайшим путям между всеми его граничными вершинами, лежащим строго внутри фрагмента. Эти расстояния формируют множество ребер непланарного графа, представляющего кратчайшие пути между граничными вершинами. Плотный граф расстояний планарного графа представляет собой объединение этих графов по всем уровням. | |||
| Строка 76: | Строка 76: | ||
== Применение == | == Применение == | ||
Задача поиска кратчайших путей давно | Задача поиска кратчайших путей давно стала предметом изучения, она находит применение в самых разных областях. Существует множество задач, сводимых к задаче поиска кратчайших путей, в которых предполагаются отрицательные веса ребер; в качестве примера можно привести поиск ориентированной схемы с минимальной средней длиной. Для планарных графов данная задача широко применяется даже в случаях, когда лежащий в основе задачи граф представляет собой решетку. Например, недавно разработанные подходы к сегментации изображений используют функцию определения отрицательных циклов [2, 3]. В числе других областей применения планарных графов можно упомянуть алгоритмы поиска сепараторов [13] и алгоритмы потока с несколькими источниками и несколькими стоками [13]. | ||
== Открытые вопросы == | |||
Клейн [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> алгоритма нахождения кратчайших путей в планарных графах с весами ребер общего вида все еще остается нерешенной. | |||
Неизвестно, как обрабатывать вставку и удаление ребер в динамической структуре данных. Возможно, потребуется введение новой структуры данных вместо плотного графа расстояний, поскольку последний определяется посредством декомпозиции. | Неизвестно, как обрабатывать вставку и удаление ребер в динамической структуре данных. Возможно, потребуется введение новой структуры данных вместо плотного графа расстояний, поскольку последний определяется посредством декомпозиции. | ||
== См. также == | == См. также == | ||
* ''[[Алгоритм поиска кратчайших путей в разреженных графах]] | * ''[[Алгоритм поиска кратчайших путей между всеми парами в разреженных графах]] | ||
* ''[[Алгоритм поиска кратчайших путей при помощи матричного произведения]] | * ''[[Алгоритм поиска кратчайших путей между всеми парами при помощи матричного произведения]] | ||
* ''[[ | * ''[[Аппроксимационные схемы для задач с планарными графами]] | ||
* ''[[Декрементный алгоритм нахождения кратчайших путей между всеми парами]] | * ''[[Декрементный алгоритм нахождения кратчайших путей между всеми парами]] | ||
* ''[[Полностью динамический алгоритм нахождения кратчайших путей между всеми парами]] | * ''[[Полностью динамический алгоритм нахождения кратчайших путей между всеми парами]] | ||
* ''[[ | * ''[[Конкурс по реализации алгоритмов поиска кратчайших путей]] | ||
* ''[[Отрицательные циклы во взвешенных орграфах]] | * ''[[Отрицательные циклы во взвешенных орграфах]] | ||
* ''[[Проверка на планарность]] | * ''[[Проверка на планарность]] | ||
* ''[[Подход к составлению расписания при помощи кратчайших путей]] | * ''[[Подход к составлению расписания при помощи кратчайших путей]] | ||
* ''[[Алгоритм поиска кратчайших путей с единственным источником]] | * ''[[Алгоритм поиска кратчайших путей с единственным источником]] | ||
== Литература == | == Литература == | ||
