Лучший алгоритм для поиска кратчайшего пути в связующем дереве от одного источника ко всем остальным узлам

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

В основном я хочу знать расстояние и путь каждой вершины из одного источника. Какое лучшее и наиболее оптимальное решение для этого, учитывая, что это остовное дерево?

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

Пожалуйста, обратите внимание на чрезмерное объяснение.


graph algorithm tree shortest-path spanning-tree
person user3903448    schedule 11.12.2014    source источник
comment
@keyser: я не против хранить расстояние каждой пары вершин, но я не должен этого делать, потому что тогда оно будет ограничено no. узлов в дереве.; Но это также хорошо на более ранней стадии.   -  person user3903448    schedule 11.12.2014
comment
Что вы планируете делать с парными расстояниями? Нет смысла внедрять LCA, если вам нужны все они.   -  person David Eisenstat    schedule 11.12.2014

Ответы (2)


arrow_upward
3
arrow_downward

Правильный способ сделать это — начать поиск в глубину с произвольного узла N, что можно сделать за линейное время. Каждый раз, когда вы сталкиваетесь с новым узлом, вы регистрируете путь, по которому вы до него добирались. Это даст вам кратчайший путь между N и каждым другим узлом в графе.

Чтобы найти кратчайший путь между узлами V и W, вы смотрите на путь от V до N и путь от N до W. Это даст вам кратчайший путь между V и W, за исключением, возможно, лишнего бита в середине, где вы нажмете N, а затем вернетесь назад. снова. Например, предположим, что путь от V до N таков:

V, A, B, C, D, E, N

а путь от N до W таков:

N, E, D, F, G, W

тогда вы можете видеть, что путь от V до W после их объединения приведет к D, а затем пойдет вверх к N через E и обратно. Это должно быть удалено из вашего пути, чтобы дать вам кратчайший путь. Другими словами, вы сканируете назад от конца первого пути и вперед по второму пути, пока не дойдете до последнего общего узла (в данном случае D), и вы отсекаете пути и соедините их вместе в этой точке, чтобы у вас осталось

V, A, B, C, D, F, G, W

Это даст вам кратчайший путь. Вы можете видеть это, потому что любой путь из V в W, который не повторяет никаких узлов, должен быть кратчайшим путем в связующем дереве.

Вот остовное дерево, взятое из Википедии в качестве примера. Если вы возьмете V как верхний левый, N как верхний правый и W как нижний левый, вы увидите, что кратчайший путь от V до W — это кратчайший путь от V до N, объединенный с кратчайшим путем от N в W, но без дублированного раздела в середине, где мы подходим к N и возвращаемся к основному пути.

Пример связующего дерева

person chiastic-security    schedule 11.12.2014

arrow_upward
2
arrow_downward

Оптимальное решение:

  1. Выбираем произвольную вершину в качестве корня и запускаем от нее поиск в глубину, чтобы вычислить dist[i] для всех i - расстояние между корнем и i-й вершиной.

  2. Расстояние между двумя произвольными вершинами u и v равно dist[u] + dist[v] - 2 * dist[lca(u, v)], где lca(u, v) — наименьший общий предок вершин u и v.

Первый шаг имеет временную сложность O(n). Временная сложность второго шага зависит от реализации поиска самого низкого общего предка. Можно достичь O(1) на запрос с линейным временем предварительной обработки (используя этот алгоритм: http://www3.cs.stonybrook.edu/~bender/newpub/BenderFa00-lca.pdf), но этот подход имеет довольно большую константу и его не очень легко реализовать. Это решение является оптимальным, потому что оно требует O(n) времени для предварительной обработки (это невозможно сделать лучше, так как вы должны хотя бы прочитать ввод) и оно отвечает на запрос за постоянное время. Вы также можете получить O(log n) времени на запрос с O(n) или O(n log n) временем предварительной обработки, используя более простые алгоритмы.

person kraskevich    schedule 11.12.2014