圖：由點“Vertex”和邊“Edge ”組成，且圖分為有向圖和無向圖(本文討論有向圖)，之前做畢業(yè)設計的時候研究“多譜流形聚類算法”的時候有研究“Graph”。高維數(shù)據(jù)的聚類就涉及到Graph Cut算法，想象數(shù)據(jù)為歐式空間的點，數(shù)據(jù)與數(shù)據(jù)之間呈現(xiàn)這樣或那樣的聯(lián)系，數(shù)據(jù)就是點，他們的聯(lián)系由邊來決定。PS：本次學習與聚類算法無關，聚類問題具體見之前寫的博客。
論：構(gòu)建好了目標對象以及目標對象的關系，接下來的大頭與研究的目的有關。比如，圖論最廣泛的應用之一：社交網(wǎng)絡。我與張三是好朋友，那么我跟張三之間就有一個Edge來表示我倆之間的聯(lián)系，張三與李四是好朋友，那張三和李四之間也有一個Edge來連接。如果我和李四之間沒關系，那么我要想聯(lián)系李四就需要通過聯(lián)系張三再通過張三來和李四產(chǎn)生聯(lián)系。一來二往，我和李四熟了，這時候我跟李四之間也有了Edge，這個時候我聯(lián)系李四的方式就不止一種了，比如我既可以通過張三聯(lián)系李四，也可以直接聯(lián)系李四，至于選擇哪種聯(lián)系方式，而這個選擇的過程中就涉及到你和張三的關系好壞程度、你與李四的好壞程度以及李四和張三的好壞程度，這種好壞程度在Graph中一般稱為“權(quán)重”，權(quán)值為正關系好，權(quán)值為負關系差，再言之，關系這種東西是以自我為中心，比如我認為我和張三的關系是很好，但張三不認為我跟他的關系很好，這里就涉及到“有向圖”。而今天討論的“論”的目標為最短路徑問題。
解決最短路徑問題的方法有很多種，本文主要探討Dijkstra最短路徑算法，通過闡述算法過程，實現(xiàn)簡單Dijkstra算法，來對最短路徑問題有一個比較深刻的了解。其次，我們知道JAVA作為面向?qū)ο蟮母呒壵Z言，有很多的輪子，我在谷歌搜了半天發(fā)現(xiàn)文檔比較友好且算法和可視化都比較良好的開源輪子，分別是：JGraphT和GraphStream，這里只討論JGraphT的調(diào)用（因為這個輪子的說明文檔很nice ^$^）。
Dijkstra算法流程
初始化：稱給定的初始節(jié)點為根節(jié)點，給每一個節(jié)點設置設定初始化的距離（距離根節(jié)點），其中，根節(jié)點的距離為0（與自身的距離當然是0），其他所有節(jié)點與根節(jié)點的距離都是無窮大（不同場景下的距離可取不同的值，如計算機中一般取整型的最大值）；創(chuàng)建兩個集合，一個集合用于收集已訪問節(jié)點，另外一個集合收集待訪問節(jié)點。
循環(huán)：對當前節(jié)點，重新計算根節(jié)點與所有鄰接點的暫時距離，將這個新計算的暫時距離與鄰接節(jié)點的當前距離進行比較取這兩個距離中較小的值去更新鄰接點的距離。比如當前節(jié)點為A,A有一個鄰接點B，其中根節(jié)點為O；若A的當前距離為W(O,A)=6，B的當前距離為W(O,B)=10，A與其鄰接點B的距離為distance(A,B)=2。則因為根節(jié)點O與A的鄰接點B的暫時距離distance(O,B)等于W(O,A)+W(A,B)=6+2=8<W(O,B)，因此W(O,B)=distance(O,B)=8，以此類推，若W(O,B)<distance(O,B)，則W(O,B)的值不變。
更新集合：當我們完成前面的根節(jié)點與當前節(jié)點的所有鄰接點的距離更新，將當前節(jié)點添加到已訪問集合中，并將當前節(jié)點從待訪問隊列中取出。
循環(huán)條件：循環(huán)的終止條件為訪問到目的節(jié)點D（求指定的OD節(jié)點之間的最短路徑）或當前節(jié)點的左右鄰接點中的距離最小為無窮大，否則就挑選距離最小的那個鄰接點作為當前節(jié)點進入步驟2的循環(huán)。
這里，我并不貼大量代碼演示算法流程，只是做一個對比，討論一下Dijkstra算法中的算法復雜度的提升上這么一個漸進的過程。
下圖圖1來自于維基百科的
網(wǎng)友評論
