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

Question

Предположим, мне дан простой ориентированный неотрицательный взвешенный граф G = (V, E) и подмножество вершин X ⊂ V. Граф находится в представлении списка смежности, а подмножество X - в виде списка. Как мне найти алгоритм, который вычисляет укороченный путь между вершинами s, t в графе, который не принадлежит X, и что всякий раз, когда путь использует две вершины в X, есть по крайней мере вершина, которая не находится в X между этими двумя вершины? Алгоритм должен быть за время O (m + nlogn).

Я думал об этом в течение долгого времени, но не смог найти алгоритм, который меньше времени O (m + nlogn), любая идея, как я может подойти к этому?

Answer 1

Предполагая m = |E| и n = |V|.

Алгоритм Дейкстры с кучей Фибоначчи выполняется в O(m + n log n). Итак, вы хотите рассмотреть дополнительное ограничение, не увеличивая окончательную временную сложность.

Если запрос о том, находится ли вершина в X, не может быть выполнен за постоянное время, вам сначала нужно сделать это, построив хэш-набор X в O(n). Последующие запросы, использующие этот хэш-набор, будут выполняться за постоянное время.

Теперь, удалив из графа ребра между парами вершин в X, просто добавим еще O(m). Затем вы можете запустить программу Дейкстры на этом новом графе с удаленными ребрами, и все это займет всего O(m + n log n) времени.