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

Question

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

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

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

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

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

Answer 1

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

Answer 2

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