介紹
對於dijkstra算法，很多人可能感覺熟悉而又陌生，可能大部分人比較瞭解bfs和dfs，而對dijkstra和floyd算法可能知道大概是圖論中的某個算法，但是可能不清楚其中的作用和原理，又或許，你曾經感覺它很難，那麼，這個時候正適合你重新認識它。
Dijkstra能是幹啥的？
Dijkstra是用來求單源最短路徑的
就拿上圖來說，假如直到的路徑和長度已知，那麼可以使用dijkstra算法計算南京到圖中所有節點的最短距離。
單源什麼意思？
從一個頂點出發，Dijkstra算法只能求一個頂點到其他點的最短距離而不能任意兩點。和bfs求的最短路徑有什麼區別？
bfs求的與其說是路徑，不如說是次數。因為bfs他是按照隊列一次一次進行加入相鄰的點，而兩點之間沒有權值或者權值相等(代價相同)。處理的更多是偏向迷宮類的這種都是隻能走鄰居(不排除特例)。Dijkstra在處理具體實例的應用還是很多的，因為具體的問題其實帶權更多一些。
比如一個城市有多個鄉鎮，鄉鎮可能有道路，也可能沒有，整個鄉鎮聯通，如果想計算每個鄉鎮到ａ鎮的最短路徑，那麼Dijkstra就派上了用場。
算法分析
對於一個算法，首先要理解它的運行流程。
對於一個Dijkstra算法而言，前提是它的前提條件和環境：
一個連通圖，若干節點，節點可能有數值，但是路徑一定有權值。並且路徑不能為負。否則Dijkstra就不適用。Dijkstra的核心思想是貪心算法的思想。不懂貪心？
貪心算法（又稱貪婪算法）是指，在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，他所做出的是在某種意義上的局部最優解。貪心算法不是對所有問題都能得到整體最優解，關鍵是貪心策略的選擇，選擇的貪心策略必須具備無後效性，即某個狀態以前的過程不會影響以後的狀態，只與當前狀態有關。
對於貪心算法，在很多情況都能用到。下面舉幾個不恰當的例子！
打個比方，吃自助餐，目標是吃回本，那麼胃有限那麼每次都僅最貴的吃。上學時，麻麻說只能帶5個蘋果，你想帶最多，那麼選五個蘋果你每次都選最大的那個五次下來你就選的最重的那個。
不難發現上面的策略雖然沒有很強的理論數學依據，或者不太好說明。但是事實規律就是那樣，並且對於貪心問題大部分都需要排序,還可能會遇到類排序。並且一個物體可能有多個屬性，不同問題需要按照不同屬性進行排序，操作。
那麼我們的Dijkstra是如何貪心的呢？對於一個點，求圖中所有點的最短路徑，如果沒有正確的方法胡亂想確實很難算出來，並且如果暴力匹配複雜度呈指數級上升不適合解決實際問題。
那麼我們該怎麼想呢？
Dijkstra算法的前提：
簡單的概括流程為：
一般從選定點開始拋入優先隊列。（路徑一般為0），boolean數組標記0的位置(最短為0) , 然後0周圍連通的點拋入優先隊列中（可能是node類），並把各個點的距離記錄到對應數組內(如果小於就更新，大於就不動，初始第一次是無窮肯定會更新)，第一次就結束了從隊列中拋出距離最近的那個點B（算法實現
package 圖論; import java.util.ArrayDeque; import java.util.Comparator; import java.util.PriorityQueue; import java.util.Queue; import java.util.Scanner; public class dijkstra { static class node { int x; //節點編號 int lenth;//長度 public node(int x,int lenth) { this.x=x; this.lenth=lenth; } } public static void main(String[] args) { int[][] map = new int[6][6];//記錄權值，順便記錄鏈接情況，可以考慮附加鄰接表 initmap(map);//初始化 boolean bool[]=new boolean[6];//判斷是否已經確定 int len[]=new int[6];//長度 for(int i=0;i<6;i++) { len[i]=Integer.MAX_VALUE; } Queueq1=new PriorityQueue(com); len[0]=0;//從0這個點開始 q1.add(new node(0, 0)); int count=0;//計算執行了幾次dijkstra while (!q1.isEmpty()) { node t1=q1.poll(); int index=t1.x;//節點編號 int length=t1.lenth;//節點當前點距離 bool[index]=true;//拋出的點確定 count++;//其實執行了6次就可以確定就不需要繼續執行了 這句可有可無，有了減少計算次數 for(int i=0;i0&&!bool[i]) { node node=new node(i, length+map[index][i]); if(len[i]>node.lenth)//需要更新節點的時候更新節點並加入隊列 { len[i]=node.lenth; q1.add(node); } } } } for(int i=0;i<6;i++) { System.out.println(len[i]); } } static Comparatorcom=new Comparator() { public int compare(node o1, node o2) { return o1.lenth-o2.lenth; } }; private static void initmap(int[][] map) { map[0][1]=2;map[0][2]=3;map[0][3]=6; map[1][0]=2;map[1][4]=4;map[1][5]=6; map[2][0]=3;map[2][3]=2; map[3][0]=6;map[3][2]=2;map[3][4]=1;map[3][5]=3; map[4][1]=4;map[4][3]=1; map[5][1]=6;map[5][3]=3; } }
執行結果：
當然，dijkstra算法比較靈活，實現方式也可能有點區別，但是思想是不變的：一個貪心思路。dijkstra執行一次就能夠確定一個點，所以只需要執行點的總和次數即可完成整個算法。
歡迎感謝小夥伴點贊、關注，贈人玫瑰，手有餘香！蟹蟹！