Кратчайший путь двух вершин в остовном дереве с ребрами на одинаковом расстоянии

Вы не можете найти кратчайший путь из вершины v в любую вершину u, имея только остовное дерево. Рассмотрим следующий граф, где стоимость всех ребер равна 1:

               v
              / \
             /   \
            /     \
           u-------w

Ясно, что кратчайший путь между v и u — это 1.

Однако рассмотрим следующее остовное дерево приведенного выше графа:

                   v
                    \
                     \
                      \
               u-------w

Если нам не дан граф, мы не можем знать, что между v и u есть ребро. Таким образом, мы можем только сказать, что существует путь от v к u через w длины 2.