給予一個加權有向圖（weighted directed graph ）G = (V, E) ，其中 V 代表頂點集合，E 代表邊集合。若以 |V|代表頂點的數量、|E|代表邊的數量且假設邊的權值皆大於 0，在最差狀況下使用 Bellman-Ford 演算法尋找某一個頂點到其他頂點的最短路徑的時間複雜度，則下列何者正確？

AO(|E|)

BO(|V||E|)正確答案

C$\mathrm{O}(|\mathbf{V}|^{2})$

D$\mathrm{O}(|\mathrm{E}|^{2})$

答案與詳解

正確答案

Bellman-Ford 演算法最差時間複雜度為 O(|V||E|)，對每個頂點鬆弛所有邊。

Bellman-Ford 執行 |V|-1 次迭代，每次鬆弛所有 |E| 條邊，故最差為 O(|V||E|)，這是此演算法的標準答案。

載入中…

Examly 收錄 38 萬+ 道歷屆題目，每題都有像這樣的精選詳解。免費下載，立即開練。