Возможно ли иметь MST, который не имеет общих ребер с кратчайшим деревом путей в неориентированном графе с различными положительными ребрами?Минимальное связующее дерево и кратчайшее дерево путей
Я пытался вывести разные примеры, но кажется, что это невозможно. Самый короткий путь пути в кратчайшем пути также должен быть включен в MST.
Учитывая алгоритм Прима, вы начинаете с вершины v и начинаете подключать к нему другие вершины таким образом, который стоит как минимум. Таким образом, для любой другой вершины у подключения к подключенному компоненту вы выращиваете с помощью алгоритма Прима (то есть тот, который включает в себя вершину V), хотя могут существовать (я думаю) вершину ж, которые могут достигать у в более коротких расстояниях, не короткий путь достижения к у от против, как алгоритм Примы диктует, что вы расширяете подсоединенный компонент вы начинаете с, перейдя в зависимости от того, узла является самым дешевым для добавления.
Следовательно, как не существует более короткий путь достижения от об к у, должно быть по крайней мере, 1 край распространены в MST генерируется исходя из об и кратчайшего пути дерева против.
Даже если корни узла MST (скажем, rootA) и кратчайшего дерево (скажем, rootB) различаются, при построении MST, алгоритм Прима должны достичь rootB используя край, который находится на самый короткий путь от rootB к rootA по кратчайшему пути дерева, так как по определению кратчайшего пути дерево должно помочь rootB достичь rootA в кратчайшем пути.
Можете ли вы уточнить, что вы имеете в виду с помощью кратчайшего дерева путей? Правильно ли я предполагаю, что это дерево кратчайших путей от конкретного узла v ко всем другим узлам? – ilim
Да, произвольно выбирая узел в качестве источника, это дерево кратчайших путей от источника ко всем другим узлам. – user3628240
Возможный дубликат http://stackoverflow.com/questions/17093814/will-a-minimum-spanning-tree -and-shortest-path-tree-always-share-at-less-one-ed? rq = 1 – Codor