Dijkstra looped tree

Question

Кто-нибудь это знает?

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

1. Сколько времени алгоритм Дейкстры требует, чтобы вычислить кратчайший путь между двумя вершинами и и V в зацикленном дереве с п узлов?
2. Опишите и проанализируйте более быстрый алгоритм.

Answer 1

Сколько времени алгоритм Дейкстры требует, чтобы вычислить кратчайшего пути между двумя вершинами и и V в зацикленной дерева с п узлов?

Это займет O(VlogV) времени (анализ наихудшего случая).
Обратите внимание, что для каждой пары узлов (u,v) существует один простой путь, который соединяет u с v. Если этот путь по какой-то причине содержит очень тяжелый взвешенный край, алгоритм Дейкста будет продолжать откладывать принятие этого края и не сможет найти правильный маршрут до тех пор, пока он не появится, что заставит алгоритм обнаружить большинство вершин в зацикливаемое дерево, делая сложность O(VlogV) (обратите внимание, что для этого графика E находится в O(V)).

Опишите и проанализируйте более быстрый алгоритм.

Поскольку существует простой путь, вам просто нужно его найти.
Это легко сделать, если найти lowest common ancestor в дереве (без петель), а затем найти маршрут к этому предку от u.
Сложность этого алгоритма O(h) - где h - высота графика.

Answer 2

Я думаю, что ответ на вопрос неправ.

В описании и анализе более быстрого алгоритма.

Вы не можете найти самый дешевый маршрут от вершины u до этого предка в O (h), поэтому этот алгоритм не O (h). По двум причинам, если внутренние узлы имеют только родительское дочернее направленное ребро, нам нужно смотреть вниз от u, чтобы найти самый дешевый маршрут к общему предку (или к корню), и я не знаю об алгоритме, который может это сделать. Вторая причина, если имеются родительские ребра parent-> child и child-> parent, то путь от исходной вершины до наименьшей общей вершины предка может быть через любую из трех смежных вершин любых внутренних узлов дерева (вершины) или одной смежной вершины (корень) любой вершины вершины листа, поэтому мы не можем сделать это в O (h).

Основываясь на моем понимании проблемы, дочерний-> родительский край не находится в определении циклического дерева. Поэтому нам нужно только спуститься по дереву и вернуться наверху, а от корня к цели - простой простой путь. Поэтому мы уменьшаем проблему до нахождения самого дешевого маршрута от u до корня, тем самым уменьшая сложность.

Кроме того, если цель является прямым потомком источника, мы остановимся при поиске самого дешевого маршрута для root. если источником является корень, проблема тривиальна, поскольку маршрут - это простой единственный путь от корня к цели, спустив поддеревья цели.