SPF(Dijkstra)算法完美教程
獨家制作SPF算法深度揭秘,一看就懂!!
摘要:
SPF(shortest path first)算法也叫Dijkstra(迪傑斯特拉)算法,由上個世紀的計算機科學家狄克斯特拉提出,是離散數學中一種經典高效的網絡(連通圖)最短路徑尋路算法.指定一個源點,求出到其餘各個頂點的最短路徑,也叫”單源最短路徑”.
應用場景:
地圖導航以及網絡路由等.
主要特點:
單個節點擁有上帝視角;以源點為中心向外層層擴充直到終點.
輸入:
已知有限個節點和唯一的源點;已知每一條邊的權重并且是正數.
循環周期:
先确認距離最短的下一跳,再更新下一跳的鄰居.
輸出:
得到從源點到剩下所有節點的最短路徑資訊.
案例拓撲圖:
以上面這張複雜的圖為例.SPF算法本來是解決有向圖的,但因為有向圖自然包括了無向圖,是以我選擇了這張更具代表性的地圖.
然後核心問題就是分别求出v0到v1~v8的最短路徑.
和Floyd-Warshall算法一樣,用二維數組MAP[][]來存放上圖每條鍊路的開銷(每條邊的權),然後計算機從這個資料庫中算出一棵棵SPF樹:
| MAP | v0 | v1 | v2 | v3 | v4 | v5 | v6 | v7 | v8 |
| 1 | 5 | ∞ | |||||||
| / | 3 | 7 | |||||||
| 2 | |||||||||
| 6 | 9 | ||||||||
| 4 | |||||||||
注意,這是一張靜态表,也就是這張表中資料是不會變化的,為了和後面要用到的動态數組區分開來.
因為是無向圖(也可了解為雙向圖),是以表格沿主對角線兩邊對稱,下三角形就用”/“代表省略.
每個單元格的行和列坐标對應了上圖中哪兩個節點之間的路徑開銷,這裡認為節點到自己的路徑開銷為0.剩下不直接相連的兩個節點之間都用”∞”表示無窮大.以上就是和Floyd-Warshall表格的不同之處.這張表也就是數字化的拓撲圖,便于程式讀取其中資料.
然後我們需要一個動态一維數組min[].它的初始狀态就是MAP中第二行(v0那一行),末狀态就是整個算法要得到的結果:v0到其餘所有節點的最短路徑開銷總值.
初狀态:
| min | |||||||||
這張表的工作模式可以類比網絡世界裡各種IP協定中司空見貫的”cost字段”,言下之意即是:先保留一個非常”劣”預設值,一遇到更優的數值就更新這個字段,直到收斂成最優為止.這張表非常重要,之後會一直用到它.其中9個字段中提前收斂到最優值(不會在減小)的已經确定的最短路徑我們稱之為”真”(在表中不妨标記為紅色數字),正好對應了C語言中bool變量的”true”.這裡展現了設定預設值的重要思想,通常把∞的大小設定成99999.
具體詳解:
做完前期準備,正式進入SPF算法每一步的詳解.
我将以上圖為例叙述一遍完整的計算過程,親愛的讀者們若是看懵逼了請别慌,後面會有一個完整的總結幫助你了解!
首先min中v0列恒為0,是以永”真”.然後非無窮的”1”和”5”是v0的全部鄰居,其中取最小的”1”就是v0到v1的最短路徑,v1列”真”.原因顯而易見,如果有其他路徑到達v1,必然要經過其他的鄰居,那些路徑(這裡隻有走v2的那條)都比”5”大,是以都排除.
此時v2列還無法确認是真,因為有可能從更近的v1出去再到達v2的某條路徑更短.是以我接下來一個動作是從v1發散到v1所有的鄰居并更新min表.
CPU檢視MAP時發現v1可到達v2,v3和v4.v0就不用去了,第一是環路,第二v0列已經是真,無法再重新整理該字段.由此v0通過v1到達v2,v3和v4的開銷為3+1,7+1,5+1.然後重新整理min表:
| 8 |
到此為止,SPF算法已經完成了第一個循環周期,即開篇所說的:先确認距離最短的下一跳(即确認真值v1),再更新下一跳的鄰居(發散v1并更新min表).專業術語中周期後半部分的”發散”被稱為”松弛”,但個人覺得前者更通俗易懂,是以下文我都用”發散”來表達這個過程.接下來進入第二個周期:
此時最小的v2列為真!!(我當時就在這個點上糾結了一個小時…)因!為!通過前兩個已經為真的v0和v1發散出去的所!有!路徑(止于鄰居)都赫然寫在min表中(4,8,6),也就是說其他到達v2的路徑長度至少也要大于6.大家如果把這一點弄明白,之後的過程就輕車熟路了.這是SPF算法的核心理論,而且這個理論就藏在算法的名字中:”最短路徑優先”!一下沒弄明白沒關系,後面根據提示回顧幾遍保你摸透它.
确認了v2以後,按照第一個周期依葫蘆畫瓢,緊接着就要以v2為中心發散到v4和v5.和之前一樣,v0和v1就不用再去了,他們已經是真了,之後不再贅述此原因.重新整理min表得:
| 11 |
第三個周期:
在v3,v4和v5中選擇最小的v4,v4列為真,原因不再贅述,标為紅色如表.再發散v4重新整理v3v5v6v7:
| 14 |
第四個周期:
v3v5v6v7中擊中v3為真,發散v3到v6:
| 10 |
第五個周期:
v5v6v7中擊中v5為真,發散v5到v7:
| 13 |
第六個周期:
v6v7中擊中v6為真,發散v6到v7v8:
| 12 | 17 |
第七個周期:
v7v8中擊中v7為真,發散v7到v8:
| 16 |
最後一步(第八個周期):
剩下唯一一個非确認字段中v8為真(既是最小也是最大).
到此算法全部結束,怎麼樣刺激吧,此時min表中記錄的就是v0到其餘各節點的最短路徑路徑成本.當然人看這篇教程習慣看拓撲圖,計算機執行指令時都是從MAP表中讀取,後面會有c語言展示.
得到最終的min表隻記錄了路徑成本(路徑的總長)并沒有記錄沿途經過的所有節點編号,然而這并不難實作,隻需再在程式裡添加一個數組沿途記錄即可，具體實作方法很簡單，就是是：每次重新整理min表之後都标明發射源點（上一跳），然後根據上一跳的遞歸就能沿最短路徑回到v0。于是最後得到的拓展min表是這樣的：
| Last Hop | \ |
完美！
總結:
總體回顧一下剛才發生的一切,我們發現在每半個周期結束後,就是在确認最小者為真之前,min表中的節點總是分成三部分:前面紅體字;中間黑體字;後面無窮大.分别對應着:已經确認真的最終數值;可能次優的臨時數值;還未被發散到的等待數值.如果把每次變化後min表中的三部分節點在剛開始的拓撲圖中區分開來,做成九張動态變化圖,就能生動形象地表現出SPF算法的根本特點:層層向外擴散,而且整個動畫正好見證了一棵SPF樹的生長過程.把這些理清楚了有助于了解用Java和C實作的算法語句.
動畫效果如下:
!!總共需要循環多少個周期呢?答案是:總共有n個節點就要循環n-1個周期.因為除了第一個節點(v0)預設真,每個周期都要讓新的一個節點成真,是以剩下n-1個節點就需要n-1個周期.當然,如果min表中第二部分有兩個并列最小的路徑成本,那麼既可以任選一個最小值也可以同時讓她們成真,然後分别發散,後者看似可以節省循環次數,但是總工作量并沒有節省!!
如果隻是想把SPF算法公式給背下來并不困難,你隻需要記住每一個循環周期内要做的兩件事情就行:先在min表第二部分中尋找最小值并标記為真,再通過被擊中的節點發散到它所有鄰居并重新整理min表.當然還是希望能通過我的講解,更好地了解算法的智慧.
C語言描述:
| #include<stdio.h> | |
| #define N 50 | |
| int main() | |
| { | |
| int n,m; //節點個數,邊的條數 | |
| int i,j; //for循環參數 | |
| bool judge[N]; //存放min表每個字段的真假值 | |
| int MAP[N][N],min[10]; | |
| int infinity=99999999; //存儲一個我們認為的正無窮值 | |
| scanf("%d %d",&n,&m); //輸入點數和邊數 | |
| for(i=0;i<n;i++) //初始化MAP表 | |
| for(j=0;j<n;j++) | |
| 15 | if(i==j) MAP[i][j]=0; |
| else MAP[i][j]=infinity; //這裡考慮到了有向圖 | |
| 18 | int a,b,c; //MAP讀入邊權時使用 |
| 19 | for(i=1;i<=m;i++) //填充每條邊權到MAP表中 |
| 20 | { |
| 21 | scanf("%d %d %d”,&a,&b,&c); |
| 22 | e[a][b]=c; |
| 23 | } |
| 24 | |
| 25 | |
| 26 | for(i=0;i<n;i++) //初始化min數組，這裡是0号點到其餘各點的初始距離 |
| 27 | min[i]=e[0][i]; |
| 28 | |
| 29 | |
| 30 | for(i=0;i<n;i++) //judge數組初始化 |
| 31 | judge[i]=false; |
| 32 | judge[0]=true; |
| 33 | |
| 34 | /*********************以下是SPF算法核心語句*********************/ |
| 35 | |
| 36 | for(i=1;i<=n-1;i++) //循環n-1次周期 |
| 37 | |
| 38 | int minimum=infinity; //給尋找min表第二部分最小值的變量賦預設值 |
| 39 | for(j=1;j<=n;j++) //找出min表第二部分距離0号點最近的節點 |
| 40 | { |
| 41 | if(judge[j]==0 && dis[j]<min) |
| 42 | { |
| 43 | minimum=min[j]; |
| 44 | m=j; |
| 45 | } |
| 46 | } |
| 47 | judge[m]=true; //把m拿來做特殊用途:标記新确認真的節點 |
| 48 | for(j=1;j<=n;j++) //沿着新确認真的節點發散到它的鄰居 |
| 49 | |
| 50 | if((e[m][j]!=infinity)&&(!judge[j]))//排除非鄰居和已經真的鄰居 |
| 51 | |
| 52 | if(min[j]>min[m]+MAP[m][j]) |
| 53 | min[j]=min[m]+MAP[m][j]; |
| 54 | |
| 55 | |
| 56 | |
| 57 | |
| 58 | /*********************以上是SPF算法核心語句*********************/ |
| 59 | |
| 60 | |
| 61 | for(i=0;i<n;i++) //輸出最終的min表 |
| 62 | printf("%d “,min[i]); |
| 63 | |
| 64 | return 0; |
| 65 | } |
| 66 |
在OSPF中的應用:
網際網路下種類繁多的路由協定中,無論是IGP還是BGP,幾乎都是路由器之間通過”口口相傳”的方式來尋路的,也就是說,它們根本不知道整個網絡地圖長什麼樣.OSPF(開放式最短路徑優先協定)提供了與衆不同的一種選路方法,也就是SPF算法.為了滿足算法的必要條件,在整個ospf網絡收斂前期,路由器之間互相交換轉發一種叫做”鍊路狀态通告(LSA)”的資料包來表述自己周邊的鍊路情況,足夠時間下來每台路由器都有了一張整個區域的線路圖和每條鍊路的帶寬開銷.後期就是以自己為源并具體進行SPF尋路,于是每台路由器都變成了一個”導航儀”.
自主導航中的實作技術:
如果你要開車從南京雨花台到北京天壇公園,先要在導航儀中設定他們為起點和終點,搜尋一條最佳路徑.而接下來導航儀負責在電子地圖中找一條從雨花台到天壇公園的最短路徑.當然這時候導航儀不可能将整個中國明細地圖納入考慮範疇,不然算出結果需要很荒唐的時間.取而代之的是劃定一定範圍内(包含起點和終點)的道路和交通管制資訊,與地點對應存儲了相關的經緯度資訊.導航儀中有個GPS接收子產品,它要接收至少四個不同方位同步導航衛星的信号,并通過這四個信号解一個三元一次方程組,以精确得到你所在的經緯度,繼而再顯示在地圖上.
新SPF算法的優化:
在上述導航儀問題中,如起始點和終點間距離過大,跨省跨州甚至跨國,這時如果按照單純的SPF計算,納入考慮範疇的節點數就過于龐大而阻礙效率,造成時間上的浪費.針對這種情況導航儀會将整個世界地圖階層化,區域化:省市之間會優選國道和高速公路,跨國越境的話就隻能将海關作為”中轉站”了.這樣一來,導航的最大計算範圍也不會超過一座城市的大小.這就是SPF算法新發展趨勢的基本思想:即階層化架構地圖,減少沿途節點.
結束語:
任何算法都有優劣.SPF算法簡單精練理想化,但是在時間複雜度上并不具絕對優勢.日常生活中如果隻是想讓計算機在最短時間内找出任意一條未必要最短的路徑,SPF顯然就不能滿足了.但無論如何,曆史悠久的SPF仍然是數學界公認最具代表性的尋路算法.
最後我想說,相比”Dijkstra”,我更喜歡”SPF”這個名字.第一,”SPF”能夠簡潔明了的暗示算法的精髓部分,第二個原因,我不太傾向于讓那些宇宙中永恒存在着的數學理論被冠以發現者的姓名,就像居裡夫人曾說過,”我的成就和作品歸屬于全人類,人們不需要時刻記住我這個發現者的身份”.
溫馨提示:文章為作者原創,字字看來皆辛苦,如需轉載請标明出處.