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