Поиск кратчайших путей в планарных графах с отрицательными весами ребер: различия между версиями

Пусть даны ориентированный граф 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 не содержит циклов отрицательной длины, вывести маркировку расстояния d для вершин-источников. В противном случае выдать сообщение, что в графе имеется цикл отрицательной длины.

Алгоритм выполняет рекурсивную декомпозицию: на каждом уровне фрагмент с n вершинами и r граничными вершинами разделяется на два подфрагмента, таких, что каждый подфрагмент содержит не более <math>2n/3 \;</math> вершин и не более <math>2r/3 + c \sqrt{n} \;</math> граничных вершин при некотором константном значении c. В данном рекурсивном контексте граничной вершиной подфрагмента считается любая граничная вершина исходного фрагмента и любая новая граничная вершина, порожденная декомпозицией фрагмента.

Уровень декомпозиции в рамках этого процесса может быть определен естественным образом. Исходный граф в целостном виде имеет 0 уровень декомпозиции, фрагменты первой декомпозиции исходного графа – 1 уровень, и так далее.