Найти минимальный общий путь от любых узлов до одного узла

Question

Моя проблема заключается в следующем.

У меня есть «резервная копия» узел и другие узлы. Из узлов тезиса мне нужно создать общий путь к узлу резервного копирования, который является минимальным (невзвешенный и неориентированный граф) Мне не нужно решение каждый раз. Просто, как я могу знать, могу ли я генерировать этот путь или нет.

Я думал о разделении графика на некоторые подграфы и поиске минимального «подпуть».

Но я не так хорош в теории графов. Я использую Python и C++.

Спасибо вам заранее.

(Извините, если есть уже вопрос, как это, я искал, но не нашел)

Answer 1

• Если вам необходимо найти узел с минимальным расстоянием до узла "резервного копирования", то BFS было бы уместно.
• Как я понял, вам нужно найти минимальный путь от нескольких (если не всех) нов в вашем графике до «резервного» узла. Для этого, я думаю, вы должны смотреть в алгоритмы, которые имеют дело с Minimum Spanning Trees
• Кроме того, я нашел другой StackOverflow вопрос, который напоминает твое: SO#1
• Вы также можете найти эту страницу полезной: Shortest Path Tree. Он не содержит никаких образцов кода, но это отправная точка. Как только вы получите теорию, я уверен, что вы либо придумаете код, либо сможете его найти.

Answer 2

так что проблема не о «кратчайшим», это о том, являются ли они подключены или нет.

вы можете сделать bfs или dfs, начиная с «резервного» узла, каждый достигший вас узел может создать путь к «резервному» узлу.

Отъезд:

http://en.wikipedia.org/wiki/Breadth-first_search
http://en.wikipedia.org/wiki/Depth-first_search