給予一個加權有向圖（weighted directed graph ）G = (V, E) ，其中 V 代表頂點集合，E 代表邊集合。若以 |V|代表頂點的數量、|E|代表邊的數量且假設邊的權值皆大於 0，在最差狀況下使用 Bellman-Ford 演算法尋找某一個頂點到其他頂點的最短路徑的時間複雜度，則下列何者正確？
AO(|E|)
BO(|V||E|)正確答案
CO(|V|2)
DO(|E|2)
答案與詳解
為什麼答案是 B
Bellman-Ford 執行 |V|-1 次迭代，每次鬆弛所有 |E| 條邊，故最差為 O(|V||E|)，這是此演算法的標準答案。
考點：低估複雜度考點：Bellman-Ford 標準複雜度考點：Dijkstra 混淆考點：干擾項
載入中…
