關於圖的常用演算法——Dijkstra單源最短路徑、Floyd多源最短路徑、Prim和Kruskal最小生成樹演算法

關於圖的常用演算法——Dijkstra單源最短路徑、Floyd多源最短路徑、Prim和Kruskal最小生成樹演算法

Dijkstra最短路徑演算法是計算某一點到其它點的最短距離的演算法。

Floyd演算法是用來計算圖中所有點之間的最短距離,它是精妙的動態規劃演算法,具體可參考:http://developer.51cto.com/art/201403/433874.htm

最小生成樹(Minimium Spanning Tree)

如果要在N個城市中鋪設網路,每個城市之間的網路建設成本不同,如何找到一個建設方案,使得所有城市能夠連通,並且總建設成本最低?這就是最小生成樹問題。

最小生成樹描詳見:https://zh.wikipedia.org/wiki/%E6%9C%80%E5%B0%8F%E7%94%9F%E6%88%90%E6%A0%91

最小生成樹有兩個基本演算法:Kruskal和Prim演算法。

Kruskal演算法是不斷選取最短的邊加入到點集中,最終是點集全連通。

Prim演算法有點類似Dijkstra演算法(參考http://www.lai18.com/content/1491510.html),從任意一點出發,選取該點最短的一條邊,將對端加入到當前點集,然後再當前點集中再選取最短的一條邊,將對端加入到當前點集,如此類推直至全部點集加入到當前點集。