Для дерева T = (V, E) найти прямой путь от вершины v к вершине w.

Question

Я застрял в своем задании алгоритма, который просит найти прямой путь в дереве (V, E) с n вершинами (ациклический непрямой граф) от вершины v к вершине w во временной сложности O(dist(v, w)). Мне нужно найти препроцесс (который запускается в O(n)) для хранения некоторой информации, чтобы я мог достичь временной сложности O(dist(v, w)).

Мне нужно некоторое представление о том, что хранить в препроцессе, что поможет позже в алгоритме.

Нет полного решения.

Я уже пытался сохранить возможный путь, но чтобы создать глобальный аджл-лист, мне нужно квадратичное время O(n^2). Также Dijkstra работает выше запрошенной сложности времени (и все алгоритмы маршрутизации для сети). Два узла в дереве имеют уникальный путь.

Также пытался использовать динамическое программирование для хранения всего пути, уже обнаруженного, но я думаю, что я получаю за линейное время. Запустите BFS и сохраните все предыдущие пути, например: (node, node) : next hop

(A, B) : B and (B, A) : A
(B, C) : C (C, B): B (A, C) : B and (C, A): B

Поэтому мне нужно (1 + 2 + 3 + 4 + 5 + ... + n - 1 + n) = n^2

Answer 1

Если ваша сеть является деревом, то каждая вершина имеет только один "входящий" край. Поэтому вам следует попробовать перейти по ссылкам от W к V (следуя входящим ребрам), а не наоборот. Это даст вам путь в обратном порядке. Сохраните его в списке и инвертируйте для получения результата.

Обратите внимание, что вам может понадобиться создать словарь вершин {child:parent}, чтобы сделать это, если у вас еще нет способа пройтись по дереву снизу вверх. Построение этого словаря займет время O(E), затем поиск пути займет время dist(V,W).