Невозможно, чтобы кратчайший путь исходного графа G между двумя вершинами был длиннее пути между теми же двумя вершинами в минимальном остовном дереве графа, или MST.
MST - это деревья или графы, которые соедините каждую вершину или узел в графе с наименьшей суммой весов ребер. Как правило, это означает, что ребра удаляются из графа для создания минимального остовного дерева.
Однако это означает, что MST может включать в себя все ребра, воссоздающие кратчайший путь между двумя вершинами по мере его появления. в G. Если MST содержит все эти ребра, то кратчайший путь между двумя вершинами в MST будет той же длины, что и кратчайший путь между двумя вершинами в G.
В противоположность этому, MST может не включать все ребра, которые воссоздают кратчайший путь G, а это означает, что две вершины были соединены с другими вершинами, используя ребра, которых нет в кратчайшем пути G. Это будет означать, что кратчайший путь между двумя вершинами в MST всегда должен быть больше (или равен, если в исходном графе несколько кратчайших путей), чем кратчайший путь в G.