貝爾曼-福特演算法維基百科,自由的 encyclopedia 貝爾曼-福特演算法(英語:Bellman–Ford algorithm),求解單源最短路徑問題的一種演算法,由理查德·貝爾曼和小萊斯特·倫道夫·福特創立。有時候這種演算法也被稱為貝爾曼-福特-摩爾演算法(Bellman–Ford–Moore algorithm),因為愛德華·F·摩爾也為這個演算法的發展做出了貢獻。它的原理是對圖進行 | V | − 1 {\displaystyle |V|-1} 次鬆弛操作,得到所有可能的最短路徑。其優於戴克斯特拉演算法的方面是邊的權值可以為負數、實現簡單,缺點是時間複雜度過高,高達 O ( | V | | E | ) {\displaystyle O(|V||E|)} 。但演算法可以進行若干種最佳化,提高了效率。 Quick Facts 貝爾曼-福特演算法, 概況 ...貝爾曼-福特演算法概況類別最短路徑問題(針對帶權有向圖)資料結構圖複雜度最壞時間複雜度 O ( | V | | E | ) {\displaystyle O\left(|V||E|\right)} 最佳時間複雜度 Θ ( | E | ) {\displaystyle \Theta (|E|)} 空間複雜度 O ( | V | ) {\displaystyle O(|V|)} 相關變數的定義Close
貝爾曼-福特演算法(英語:Bellman–Ford algorithm),求解單源最短路徑問題的一種演算法,由理查德·貝爾曼和小萊斯特·倫道夫·福特創立。有時候這種演算法也被稱為貝爾曼-福特-摩爾演算法(Bellman–Ford–Moore algorithm),因為愛德華·F·摩爾也為這個演算法的發展做出了貢獻。它的原理是對圖進行 | V | − 1 {\displaystyle |V|-1} 次鬆弛操作,得到所有可能的最短路徑。其優於戴克斯特拉演算法的方面是邊的權值可以為負數、實現簡單,缺點是時間複雜度過高,高達 O ( | V | | E | ) {\displaystyle O(|V||E|)} 。但演算法可以進行若干種最佳化,提高了效率。 Quick Facts 貝爾曼-福特演算法, 概況 ...貝爾曼-福特演算法概況類別最短路徑問題(針對帶權有向圖)資料結構圖複雜度最壞時間複雜度 O ( | V | | E | ) {\displaystyle O\left(|V||E|\right)} 最佳時間複雜度 Θ ( | E | ) {\displaystyle \Theta (|E|)} 空間複雜度 O ( | V | ) {\displaystyle O(|V|)} 相關變數的定義Close