Наименьшее расстояние пути от источника (ов) до всех узлов в графике - O (m + n log (n)) время - PullRequest
Новая
       82

Наименьшее расстояние пути от источника (ов) до всех узлов в графике - O (m + n log (n)) время

0 голосов
/ 02 февраля 2020

Пусть G (V, E) - ориентированный взвешенный граф с длинами ребер, где все длины ребер положительны, кроме двух ребер с отрицательными длинами. Для фиксированной вершины s задайте алгоритм, вычисляющий кратчайшие пути из s в любую другую вершину за O (e + v log (v)).

Моя работа:

Я думаю об использовании метода перевеса алгоритма Джонсона. А затем, запустите Belford Al go один раз и примените Dijkstra v раз. Это даст мне временную сложность как O (v ^ 2 log v + ve). Это стандартная самая короткая задача из всех пар, так как мне нужна только одна вершина (и) - моя временная сложность будет O (v log v + e), верно?

1 Ответ

2 голосов
/ 02 февраля 2020

Для такого рода проблем изменение графика часто намного проще, чем изменение алгоритма. Назовем два ребра с отрицательным весом N1 и N2; путь по определению не может использовать один и тот же край более одного раза, поэтому существует четыре вида пути:

  • A. Те, которые не используют ни N1, ни N2,
  • B. Те, которые используют N1, но не N2,
  • C. Те, которые используют N2, но не N1,
  • D. Те, которые используют как N1, так и N2.

Таким образом, мы можем построить новый граф с четырьмя копиями каждого узла из исходного графа, так что для каждого узла u в исходном графе, (u, A), (u, B), (u, C) и (u, D) являются узлами в новом графе. Ребра в новом графике выглядят следующим образом:

  • Для каждого ребра положительного веса u-v в исходном графике в новом графике есть четыре копии этого ребра, (u, A)-(v, A) ... (u, D)-(v, D). Каждое ребро в новом графе имеет тот же вес, что и соответствующее ребро в исходном графе.
  • Для первого ребра с отрицательным весом (N1) в новом графе есть две копии этого ребра; один из слоя A в слой B, а другой из слоя C в слой D. Эти новые ребра имеют вес 0.
  • Для второго ребра с отрицательным весом (N2) существует две копии этого ребра в новом графике; один от слоя A к слою C, а другой от слоя B к слою D. Эти новые ребра имеют вес 0.

Теперь мы можем запустить любую стандартную задачу с кратчайшим путем из одного источника, например Алгоритм Дейкстры, только один раз на новом графике. Кратчайший путь от источника до узла u в исходном графе будет одним из следующих четырех путей в новом графе, в зависимости от того, какой путь будет иметь наименьший вес в исходном графе:

  • (source, A) до (u, A) с тем же весом.
  • (source, A) до (u, B) с весом в новом графике минус вес N1.
  • (source, A) до (u, C) с весом в новом графике минус вес N2.
  • (source, A) до (u, D) с весом в новом графике минус веса N1 и N2.

Поскольку новый граф имеет вершины 4V и 4E - 2 ребра, наихудшая производительность алгоритма Дейкстры равна O((4E - 2) + 4V log 4V), которая при необходимости упрощается до O(E + V log V).

Чтобы обеспечить кратчайший путь в новом графе соответствует подлинному пути в исходном графе, остается доказать, что путь от, например, (source, A) до (u, B) не будет использовать две копии одного ребра из исходного графа. Это довольно легко показать, но я оставлю это вам, чтобы подумать.

...