Создайте алгоритм вычисления кратчайшего пути с ограничениями на вершины в O (m + nlogn) - PullRequest
Новая
       36

Создайте алгоритм вычисления кратчайшего пути с ограничениями на вершины в O (m + nlogn)

0 голосов
/ 08 мая 2020

Итак, я пытаюсь написать алгоритм для вычисления кратчайшего пути с ограничениями на вершины, которые вы можете посетить за время O (m + nlogn). В этой задаче нам дан косвенный взвешенный (неотрицательный) граф G = (V, E), набор вершин X ⊂ V и две вершины s, t ∈ V \ X. Граф задан списками смежности и мы можем предположить, что для определения того, находится ли вершина в X, требуется O (1) времени. Я пытаюсь написать алгоритм, который может вычислить кратчайший путь между s и t в G, так что путь включает не более одной вершины из X, если такой путь существует за время O (m + nlogn). Я знаю, что для этого алгоритма потребуется модифицированный алгоритм Дейкстры, но я не знаю, как действовать дальше. Может ли кто-нибудь помочь мне? Спасибо

Ответы [ 2 ]

0 голосов
/ 08 мая 2020

Есть возможность удвоить количество вершин не в X .

Для каждой вершины v не в X , вы создаете v0 и v1 : v0 доступен только без перехода из вершины в X , v1 доступен через одну и только одну вершину в X .

Назовем w другую вершину. Тогда: 

   if w is in X, v not in X:
        length (w, v0) = infinite and dist(v1) = min (dist(v1), dist(w) + length(w, v))

    if w is in X, v in X:
        length (w, v) = infinite 

    if w is not in X, v not in X:
        dist (v0) = min (dist(v0), dist (w0) + length (w, v))
        dist (v1) = min (dist(v1), dist (w1) + length (w, v))

    if w is not in X, v is in X:
        dist (v) = min (dist(v), dist (w0) + length (w, v))
0 голосов
/ 08 мая 2020

Постройте новый граф, взяв две непересекающиеся копии вашего графа G (назовите их G0 и G1), и для каждого ребра (v, x) в G (с x в X) добавьте дополнительное ребро в объединенный граф от v в G0 до x в G1. Этот новый граф имеет в два раза больше вершин, чем G, и не более чем в три раза больше ребер.

Кратчайший путь от s в G0 до t в G1 - это кратчайший путь от s до t в G, проходящий в точке минимум одна вершина X.

На этом новом графе алгоритм Дейкстры (с приоритетной очередью, реализованной с помощью кучи Фибоначчи) работает за время O (3m + 2n log 2n) = O (m + n log n) .

...