Расстояние от набора вершин в ориентированном графе

Я разрабатываю алгоритм для нахождения минимального расстояния данной вершины v от подмножества вершин A (то есть от элемента этого подмножества). Мне нужно найти значение k такое, что:

  • расстояние от x до v равно k, для некоторого x в A
  • расстояние от y до v равно >=k для всех y в A.

Мое решение состоит в:

  • получение графа транспонирования G'
  • посещение G', начиная с v, используя BFS.
  • найти минимальное расстояние от вершин в A

И я думаю, что это работает и должно выполняться за время O(|V|+|E|). Мой вопрос: есть лучшее решение этой проблемы?


algorithm traversal graph-theory
person Jubstuff    schedule 21.09.2011    source источник
comment
Является ли граф взвешенным и может ли он иметь отрицательные веса?   -  person flight    schedule 21.09.2011
comment
Нет, график не взвешен.   -  person Jubstuff    schedule 21.09.2011

Ответы (2)


arrow_upward
1
arrow_downward

Нет, лучшего решения нет.
Рассмотрите следующее: 1-2-3-4,A={4}, v=1. вам придется повторить все V, E в графе [вы должны прочитать весь путь], сделав эту задачу Omega(V+E). поскольку ваш алгоритм правильный [просто доказать] и O(V+E) [тривиально, создание G' и BFS], а проблема Omega(V+E), ваше решение является оптимальным с точки зрения нотации большого O.

person amit    schedule 21.09.2011

arrow_upward
0
arrow_downward

Нет надежды на улучшение асимптотического наихудшего случая, но практическая оптимизация — это поиск одновременно от A и v до тех пор, пока поиски не встретятся (всегда выбирайте обновление меньшей границы).

person the guy formerly known as d    schedule 21.09.2011