圖形的平均最短路徑長度和直徑算法的時間複雜度是否有區別？

Question

對於無向未加權圖，算法計算其平均最短路徑長度vs與計算圖的直徑的算法的複雜度（即兩個圖之間最長的最短路徑頂點？

Answer 1

根據Wikipedia，要計算圖的直徑，首先應該找到所有對最短路徑。在計算完全對最短路徑後，兩種算法都減少到O（V^2）計算，因此它們的複雜性是相同的。

Answer 2

不，兩者之間的時間複雜性不應有任何差異。

通過調整最短路徑算法，您可以找到兩個頂點之間最長的路徑。

Answer 3

我還沒有閱讀關於這個問題的很多文獻，但我懷疑這兩者是相同的。但是，如果有差異，我會說計算圖的直徑可能漸近地快。

我的兩種算法都是使用Dijkstra算法在V*(E+V*log(V))中運行計算所有對最短路徑。那麼你的平均值就是所有這些值的算術平均值。我看不到一種可以加快速度的方法。

但是，對於計算圖的直徑，可能有一些巧妙的技巧可以用來加速此過程。但是作爲一個上界，你可以簡單地通過所有對最短路徑上的上確界來得到直徑，其具有與計算平均最短路徑相同的運行時複雜度。