計算機概論、大意(資訊科學概論,電腦常識,電子計算機概論)題庫下載題庫

最小生成樹演算法

Prim演算法與Kruskal演算法是尋找最小生成樹的經典方法，兩者皆為貪心法，通常使用二元堆積，時間複雜度為 。若使用斐波那契堆，Prim演算法可加速至 。

貝爾曼-福特演算法（英語：Bellman–Ford algorithm），求解單源最短路徑問題的一種演算法，由理察·貝爾曼（Richard Bellman） 和 萊斯特·福特 創立的。有時候這種演算法也被稱為 Moore-Bellman-Ford 演算法，因為 Edward F. Moore 也為這個演算法的發展做出了貢獻。它的原理是對圖進行V-1次鬆弛操作，得到所有可能的最短路徑。其優於迪科斯徹演算法的方面是邊的權值可以為負數、實現簡單，缺點是時間複雜度過高，高達{displaystyle O(VE)}。但演算法可以進行若干種最佳化，提高了效率。