4446
правок
Поиск кратчайших путей в планарных графах с отрицательными весами ребер: различия между версиями
Материал из WEGA
Поиск кратчайших путей в планарных графах с отрицательными весами ребер (посмотреть исходный код)
Версия от 14:17, 12 мая 2016
, 12 мая 2016→Нотация
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 10: | Строка 10: | ||
== Нотация == | == Нотация == | ||
Пусть даны ориентированный граф G = (V, E) и весовая функция w: E | Пусть даны ориентированный граф 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>. | ||
Задача 1 (Поиск кратчайших путей с единственным источником) | '''Задача 1 (Поиск кратчайших путей с единственным источником)''' | ||
Дано: ориентированный граф G = (V, E), весовая функция w: E | Дано: ориентированный граф G = (V, E), весовая функция <math>w: E \to \mathbb{R} \;</math>, вершина-источник <math>s \in V \;</math>. | ||
Требуется: если граф G не содержит циклов отрицательной длины, вывести маркировку расстояния d для вершин-источников. В противном случае выдать сообщение, что в графе имеется цикл отрицательной длины. | Требуется: если граф G не содержит циклов отрицательной длины, вывести маркировку расстояния d для вершин-источников. В противном случае выдать сообщение, что в графе имеется цикл отрицательной длины. | ||
Алгоритм Факчаренфола и Рао [ ] предназначен для случая планарных графов и выполняется за время O(n log n), улучшив время O( | Алгоритм Факчаренфола и Рао [4] предназначен для случая планарных графов и выполняется за время <math>O(n \; log^3 \; n)</math>, улучшив время <math>O(n^{3/2}) \;</math> алгоритма Липтона, Роуза и Тарьяна [9] и <math>O(n^{4/3} \; log \; nL)</math> – алгоритма Хензингера, Клейна, Рао и Субраманиама [6]. | ||
Этот алгоритм, как и все предыдущие, использует технику рекурсивной декомпозиции и строит структуру данных под названием «плотный граф расстояний», которая будет описана ниже. | Этот алгоритм, как и все предыдущие, использует технику рекурсивной декомпозиции и строит структуру данных под названием «плотный граф расстояний», которая будет описана ниже. | ||
Декомпозиция графа представляет собой множество подмножеств | [[Декомпозиция графа]] представляет собой множество подмножеств <math>P_1, P_2, ..., P_k \;</math> (не обязательно непересекающихся), таких, что объединение всех подмножеств равно V и для всех ребер <math>e = (u, v) \in E \;</math> существует уникальное множество <math>P_i \;</math>, содержащее e. Вершина v является [[граничная вершина|граничной вершиной]] множества <math>P_i \;</math>, если <math>v \in P_i \;</math> и существует ребро e = (v, x), такое, что <math>x \notin P_i \;</math>. Подграф, порожденный на подмножестве <math>P_i \;</math>, называется фрагментом декомпозиции. | ||
| Строка 49: | Строка 49: | ||
Пусть дано вложение фрагмента. Дыра представляет собой ограниченную грань, в которой все смежные вершины являются граничными вершинами. В идеале можно надеяться на то, что существует планарное вложение любого фрагмента рекурсивной декомпозиции, в котором все граничные вершины располагаются на одной грани и упорядочены по кругу, т.е. в каждом фрагменте не имеется дыр. Это не всегда оказывается верным, но алгоритм работает с любой декомпозицией с константным количеством дыр в каждом фрагменте. Эту декомпозицию можно найти за время O(n log n) при помощи алгоритма Миллера [12] для поиска простого циклического сепаратора. | Пусть дано вложение фрагмента. Дыра представляет собой ограниченную грань, в которой все смежные вершины являются граничными вершинами. В идеале можно надеяться на то, что существует планарное вложение любого фрагмента рекурсивной декомпозиции, в котором все граничные вершины располагаются на одной грани и упорядочены по кругу, т.е. в каждом фрагменте не имеется дыр. Это не всегда оказывается верным, но алгоритм работает с любой декомпозицией с константным количеством дыр в каждом фрагменте. Эту декомпозицию можно найти за время O(n log n) при помощи алгоритма Миллера [12] для поиска простого циклического сепаратора. | ||
== Основные результаты == | == Основные результаты == | ||
