設計一個圖，其中最短路徑樹比最小生成樹長

Question

設計一個圖的示例，其中shortest path tree比最小生成樹長。

在最壞的情況下，最短路徑樹比最小生成樹多長時間？

Answer 1

考慮以下圖，其中一個邊緣的成本括號之間寫成：

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

然後，在頂點1爲根的最短路徑樹是：

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

而最小生成樹的圖是：

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

至於你的第二個問題，我想不出一個nswer。

Answer 2

回答你的第二個問題：如果圖有n個頂點，最短路徑樹的長度是L，最小生成樹的長度是K，那麼L <（n-1）K L可以任意接近（n-1）K。爲了明白爲什麼K最短路徑樹中的每條邊都小於最小生成樹的長度。有（n-1）個，所以最短路徑樹的長度小於（n-1）K。但差異可以任意小。

考慮其中頂點1距離頂點2，...，n的距離M（一個非常大的數）的圖。 2，...，n中任何兩個頂點的距離都是非常小的數e。那麼根長爲1的短路徑樹的長度爲（n-1）M，而最小生成樹的長度爲（n-2）e + M。當e爲非常小，而且M非常大。