最短路徑算法

　　四、Dijkstra

　　Dijkstra 算法，又叫迪科斯徹算法（Dijkstra），

　　算法解決的是有向圖中單個源點到其他頂點的最短路徑問題。

　　此Dijkstra 算法已在本BLOG內(nèi)倆篇文章中，有所具體闡述，請參見：

　　I、經(jīng)典算法研究系列：二、Dijkstra 算法初探

　　http://blog.csdn.net/v_JULY_v/archive/2010/12/24/6096981.aspx

　　II、經(jīng)典算法研究系列：二之續(xù)、徹底理解Dijkstra算法

　　http://blog.csdn.net/v_JULY_v/archive/2011/02/13/6182419.aspx

　　五、Bellman-Ford

　　Bellman-Ford：

　　求單源最短路，可以判斷有無負(fù)權(quán)回路（若有，則不存在最短路），

　　時效性較好，時間復(fù)雜度O（VE）。

　　附：

　　SPFA：

　　是Bellman-Ford的隊列優(yōu)化，時效性相對好，時間復(fù)雜度O（kE）。（k《《V）。

　　六、Floyd-Warshall

　　Floyd-Warshall：求多源、無負(fù)權(quán)邊的最短路。用矩陣記錄圖。時效性較差，時間復(fù)雜度O（V^3）。此算法是解決任意兩點間的最短路徑的一種算法，可以正確處理有向圖或負(fù)權(quán)的最短路徑問題。

　　更多，請參考：

　　幾個最短路徑算法比較：

　　http://blog.csdn.net/v_JULY_v/archive/2011/02/12/6181485.aspx

　　附：Kneser圖

　　Kneser圖是與圖的分?jǐn)?shù)染色有關(guān)的算法。

　　給定正整數(shù)a，b，a≥2b，Kneser圖Ka:b是以如下方式定義的一個圖：

　　其頂點是從給定的a個元素的集合中選出的b個元素構(gòu)成的子集，兩頂點間有邊當(dāng)且僅當(dāng)這兩個頂點為不交的集合。

　　最小生成樹

　　七、Prim

　　八、Kruskal

　　此最?。?quán)值）生成樹的倆種算法，日后，會在本BLOG內(nèi) 具體而深入闡述。

　　圖匹配

　　九、匈牙利算法

　　匈牙利算法是眾多用于解決線性任務(wù)分配問題的算法之一，是用來解決二分圖最大匹配問題的經(jīng)典算法，可以在多項式時間內(nèi)解決問題，由匈牙利數(shù)學(xué)家Jack Edmonds于1965年提出。

　　這個算法，比較生疏，下面，稍微闡述下：

　　I、匈牙利算法應(yīng)用問題的描述：

　　設(shè)G=（V，E）是一個無向圖。如頂點集V可分區(qū)為兩個互不相交的子集V1，V2之并，并且圖中每條邊依附的兩個頂點都分屬于這兩個不同的子集。則稱圖G為二分圖。二分圖也可記為G=（V1，V2，E）。

　　給定一個二分圖G，在G的一個子圖M中，M的邊集{E}中的任意兩條邊都不依附于同一個頂點，則稱M是一個匹配。 選擇這樣的子集中邊數(shù)最大的子集稱為圖的最大匹配問題（maximal matching problem）

　　如果一個匹配中，圖中的每個頂點都和圖中某條邊相關(guān)聯(lián)，則稱此匹配為完全匹配，也稱作完備，完美匹配。

　　II、算法描述

　　求最大匹配的一種顯而易見的算法是：先找出全部匹配，然后保留匹配數(shù)最多的。但是這個算法的時間復(fù)雜度為邊數(shù)的指數(shù)級函數(shù)。因此，需要尋求一種更加高效的算法。

　　下面介紹用增廣路求最大匹配的方法（稱作匈牙利算法，匈牙利數(shù)學(xué)家Edmonds于1965年提出）。

　　增廣路的定義（也稱增廣軌或交錯軌）：

　　若P是圖G中一條連通兩個未匹配頂點的路徑，并且屬于M的邊和不屬于M的邊（即已匹配和待匹配的邊）在P上交替出現(xiàn)，則稱P為相對于M的一條增廣路徑。

　　由增廣路的定義可以推出下述三個結(jié)論：

　　1－P的路徑長度必定為奇數(shù)，第一條邊和最后一條邊都不屬于M。

　　2－將M和P進行異或操作（去同存異）可以得到一個更大的匹配M’。

　　3－M為G的最大匹配當(dāng)且僅當(dāng)不存在M的增廣路徑。

　　算法輪廓：

　?。?）置M為空

　　（2）找出一條增廣路徑P，通過異或操作獲得更大的匹配M’代替M

　?。?）重復(fù)（2）操作直到找不出增廣路徑為止

　　III、時間復(fù)雜度與空間復(fù)雜度

　　時間復(fù)雜度

　　鄰接矩陣：最壞為O（n^3） 鄰接表：O（mn）

　　空間復(fù)雜度：

　　鄰接矩陣：O（n^2） 鄰接表：O（m+n）

　　附：

　　Edmonds‘s matching

　　強連通分支算法與網(wǎng)絡(luò)流

　　十、Ford-Fulkerson

　　最大流量算法（Ford-Fulkerson Algorithm），

　　也叫做貝爾曼-福特算法，被用于作為一個距離向量路由協(xié)議例如RIP， BGP， ISO IDRP， NOVELL IPX的算法。

　　附：Edmonds-Karp、Dinic、Push-relabel、maximum flow

　　強連通分支算法：

　　Kosaraju、 Gabow、 Tarjan。

　　此類算法，日后闡述。

　　完。