построить граф, в котором дерево кратчайших путей длиннее минимального остовного дерева

Рассмотрим следующий график, где стоимость ребра указана между фигурными скобками:

1
|
|(1)
|
2
| \
|  \
|   \
|    \
|(25) \ (10)
|      \
3-------4     
   (20)

Тогда дерево кратчайших путей с корнем в вершине 1:

1
|
|(1)
|
2
| \
|  \
|   \
|    \
|(25) \ (10)
|      \
3       4    

в то время как минимальное остовное дерево графа:

1
|
|(1)
|
2
  \
   \
    \
     \
      \ (10)
       \
3-------4     
   (20)

Что касается вашего второго вопроса, я не нашел ответа.

Чтобы ответить на ваш второй вопрос: если граф имеет n вершин, длина дерева кратчайших путей равна L, а длина минимального остовного дерева равна K, то L ‹(n-1)K, но L может быть произвольно близко к (n-1)K. Чтобы понять, почему L ‹ (n-1)K : каждое ребро в дереве кратчайших путей меньше длины минимального остовного дерева. Их (n-1), следовательно, длина дерева кратчайших путей меньше (n-1)K. Но разница может быть сколь угодно малой.

Рассмотрим граф, в котором вершина 1 находится на очень большом расстоянии M от вершины 2,...,n. Расстояния между любыми двумя вершинами среди 2,...,n равны очень малому числу e. Тогда длина дерева коротких путей с корнем в 1 равна (n-1)M, тогда как длина минимального остовного дерева равна (n-2)e + M. Отношение приблизительно равно (n-1), когда e равно очень маленький, а М очень большой.