Данный граф G с корневым узлом r образует ли кратчайшие пути от корня ко всем остальным вершинам дерево? Другими словами, если вы выберете кратчайший путь из r во все остальные вершины и объедините их, получится дерево?
Образуют ли кратчайшие пути от узла графа ко всем остальным дерево?
user16505641
8 августа 2021 в 21:45
55
1
Ответы (1)
templatetypedef
8 августа 2021 в 22:35
Да, почти.
Дерево кратчайших путей — это дерево с корнем в узле v, в котором прослеживаются кратчайшие пути от v до каждого другого узла.
Если вы выберете кратчайшие пути от узла v к другому узлу, это может не сформировать дерево, но это всегда будет DAG. Оно не всегда будет деревом, если существуют два или более разных кратчайших пути из v в некоторый узел u. Но в этом случае вы можете удалить некоторые ребра, чтобы преобразовать его в дерево.
Подводя итог, если я найду кратчайший путь от корня к вершине u и кратчайший путь от корня к вершине v и объединим два пути, образующих дерево, это правильно?
Не всегда. Если есть два разных кратчайших пути от r к u, и кратчайший путь от r к v проходит через u, вы можете получить DAG, не являющийся деревом. Но было бы легко преобразовать это в дерево.