ACM最短路徑算法.ppt

《ACM最短路徑算法.ppt》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、最短路徑算法問題引入：中二尚、菜雞然和小水虎從哈爾濱出發(fā)去寧波參加第二屆CCPC全國總決賽，但是因?yàn)闆]有直達(dá)的火車票，而且學(xué)校窮，不給報(bào)銷飛機(jī)票?，F(xiàn)在已知可以從任意車站中轉(zhuǎn)，也知道任意兩個(gè)車站之間的票價(jià)，聰明的你們能否算出他們能參加比賽的最小花費(fèi)？求圖中任意兩點(diǎn)之間的最短路徑。最近公共祖先LCADijkstra算法及其隊(duì)列優(yōu)化1Bellman-Ford算法2SPFA（Bellman-Ford隊(duì)列優(yōu)化）3BFS求單源最短路徑4Floyd-Warshell算法5Dijkstra算法及其隊(duì)列優(yōu)化Dijkstra算法及其隊(duì)列優(yōu)化Dijkstra算法及

2、其隊(duì)列優(yōu)化Dijkstra算法及其隊(duì)列優(yōu)化Dijkstra算法優(yōu)化：從算法過程和代碼中我們可以知道，Dijkstra算法的時(shí)間浪費(fèi)在了每次都要遍歷所有點(diǎn)去尋找當(dāng)前dist數(shù)組中的最小值，所以我們可以很輕易地想出利用堆或優(yōu)先隊(duì)列的方式對算法進(jìn)行優(yōu)化。優(yōu)化后的Dijkstra算法時(shí)間復(fù)雜度為O（ElogV）Bellman-Ford算法Bellman-Ford算法中邊權(quán)可正可負(fù)，并且可以判斷圖中是否存在負(fù)環(huán)，而Dijkstra算法無法處理邊權(quán)為負(fù)數(shù)的情況。第一，初始化所有點(diǎn)。第二，進(jìn)行循環(huán)，遍歷所有的邊，進(jìn)行松弛計(jì)算。第三，遍歷圖中所有的邊edge

3、（u，v），判斷是否存在這樣情況：d（v）>d(u)+w(u,v)有則返回false，表示途中存在從源點(diǎn)可達(dá)的權(quán)為負(fù)的回路。Bellman-Ford算法數(shù)組dist[i]記錄從源點(diǎn)s到頂點(diǎn)i的路徑長度初始化dist[i]為無窮大，表示不可達(dá)，dist[s]=0for(inti=1;i

4、994年發(fā)表的。設(shè)立一個(gè)先進(jìn)先出的隊(duì)列用來保存待優(yōu)化的結(jié)點(diǎn)，優(yōu)化時(shí)每次取出隊(duì)首結(jié)點(diǎn)u，并且用u點(diǎn)當(dāng)前的最短路徑估計(jì)值對離開u點(diǎn)所指向的結(jié)點(diǎn)v進(jìn)行松弛操作，如果v點(diǎn)的最短路徑估計(jì)值有所調(diào)整，且v點(diǎn)不在當(dāng)前的隊(duì)列中，就將v點(diǎn)放入隊(duì)尾。這樣不斷從隊(duì)列中取出結(jié)點(diǎn)來進(jìn)行松弛操作，直至隊(duì)列空為止。SPFA算法定理：只要最短路徑存在，上述SPFA算法必定能求出最小值。證明：每次將點(diǎn)放入隊(duì)尾，都是經(jīng)過松弛操作達(dá)到的。換言之，每次的優(yōu)化將會有某個(gè)點(diǎn)v的最短路徑估計(jì)值d[v]變小。所以算法的執(zhí)行會使d越來越小。由于我們假定圖中不存在負(fù)權(quán)回路，所以每個(gè)結(jié)點(diǎn)都有最短

5、路徑值。因此，算法不會無限執(zhí)行下去，隨著d值的逐漸變小，直到到達(dá)最短路徑值時(shí)，算法結(jié)束，這時(shí)的最短路徑估計(jì)值就是對應(yīng)結(jié)點(diǎn)的最短路徑值。SPFA算法SPFA是這樣判斷負(fù)環(huán)的：如果某個(gè)點(diǎn)進(jìn)入隊(duì)列的次數(shù)超過N次則存在負(fù)環(huán)（SPFA無法處理帶負(fù)環(huán)的圖）期望的時(shí)間復(fù)雜度：O(ke)，其中k為所有頂點(diǎn)進(jìn)隊(duì)的平均次數(shù)，可以證明k一般小于等于2但是SPFA在最壞情況下會退化成Bellman算法。最壞時(shí)間復(fù)雜度為O（VE）SPFA算法SPFA算法有兩個(gè)優(yōu)化算法SLF和LLL：SLF：SmallLabelFirst策略，設(shè)要加入的節(jié)點(diǎn)是j，隊(duì)首元素為i，若dis

6、t(j)nRELAX(u,i)；如果不在隊(duì)列中，vis[i]=true，cnt[i]++，如果入隊(duì)次數(shù)大于等于n，returnfalse，入隊(duì)。BFS求單源

7、最短路徑在我們學(xué)習(xí)圖的基本算法BFS和DFS的時(shí)候，其實(shí)那就是一個(gè)求解每一步的權(quán)重都為1的最短路，那么權(quán)重不為1的情況我，我們是否繼續(xù)使用呢？采用鄰接表或前向星進(jìn)行圖的存儲，則BFS的時(shí)間復(fù)雜度為：開始的初始化O(V)+BFS操作O(E)=O(V+E)BFS求單源最短路徑源點(diǎn)入隊(duì)且當(dāng)前總距離為0While(隊(duì)列非空){取隊(duì)首元素并popif(隊(duì)首為終點(diǎn))返回總距離點(diǎn)標(biāo)記為訪問過遍歷隊(duì)首點(diǎn)相連的所有點(diǎn){if(點(diǎn)沒被訪問)這個(gè)點(diǎn)和總距離加上這個(gè)邊權(quán)入隊(duì)}}Floyd-Warshell算法求傳遞閉包基本思想：dp[i][j]=min(dp[i][k

8、]+dp[k][j],dp[i][j])記得循環(huán)順序：k--->i--->j!!!