最短路徑—弄懂Dijkstra(迪傑斯特拉)算法
- 2019 年 10 月 6 日
- 筆記
看前點個關注、蟹蟹
介紹
對於 dijkstra算法，很多人可能感覺熟悉而又陌生，可能大部分人比較了解 bfs和dfs，而對dijkstra和floyd算法可能知道大概是圖論中的某個算法，但是可能不清楚其中的作用和原理，又或許，你曾經感覺它很難，那麼，這個時候正適合你重新認識它。
Dijkstra能是幹啥的？
Dijkstra是用來求單源最短路徑的
就拿上圖來說，假如知道的路徑和長度已知，那麼可以使用 dijkstra算法計算南京到圖中所有節點的最短距離。
單源什麼意思？
- 從一個頂點出發，Dijkstra算法只能求一個頂點到其他點的最短距離而不能任意兩點。
和 bfs求的最短路徑有什麼區別？
bfs求的與其說是路徑，不如說是次數。因為bfs他是按照隊列一次一次進行加入相鄰的點，而兩點之間沒有權值或者權值相等(代價相同)。處理的更多是偏向迷宮類的這種都是只能走鄰居(不排除特例)。
Dijkstra在處理具體實例的應用還是很多的，因為具體的問題其實帶權更多一些。
比如一個城市有多個鄉鎮，鄉鎮可能有道路，也可能沒有，整個鄉鎮聯通，如果想計算每個鄉鎮到ａ鎮的最短路徑，那麼Dijkstra就派上了用場。
算法分析
對於一個算法，首先要理解它的運行流程。對於一個Dijkstra算法而言，前提是它的前提條件和環境：
- 一個連通圖，若干節點，節點可能有數值，但是
路徑一定有權值。並且路徑不能為負。否則Dijkstra就不適用。
Dijkstra的核心思想是貪心算法的思想。不懂貪心？
貪心算法（又稱貪婪算法）是指，在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，他所做出的是在某種意義上的局部最優解。貪心算法不是對所有問題都能得到整體最優解，關鍵是貪心策略的選擇，選擇的貪心策略必須具備無後效性，即某個狀態以前的過程不會影響以後的狀態，只與當前狀態有關。
對於貪心算法，在很多情況都能用到。下面舉幾個不恰當的例子！
打個比方，吃自助餐，目標是吃回本，那麼胃有限那麼每次都僅最貴的吃。 上學時，麻麻說只能帶5個蘋果，你想帶最多，那麼選五個蘋果你每次都選最大的那個五次下來你就選的最重的那個。
不難發現上面的 策略雖然沒有很強的理論數學依據，或者不太好說明。但是事實規律就是那樣，並且對於貪心問題大部分都需要排序,還可能會遇到類排序。並且一個物體可能有多個屬性，不同問題需要按照不同屬性進行排序，操作。
那麼我們的 Dijkstra是如何貪心的呢？對於一個點，求圖中所有點的最短路徑，如果沒有正確的方法胡亂想確實很難算出來，並且如果暴力匹配複雜度呈指數級上升不適合解決實際問題。
那麼我們該怎麼想呢？
Dijkstra算法的前提：
- 首先，Dijkstra處理的是帶正權值的
有權圖，那麼，就需要一個二維數組（如果空間大用list數組）存儲各個點到達(邊)的權值大小。(鄰接矩陣或者鄰接表存儲) - 其次，還需要一個boolean數組判斷那些點已經確定最短長度，那些點沒有確定。int數組記錄距離(在算法執行過程可能被多次更新)。
- 需要優先隊列加入已經確定點的周圍點。每次拋出確定最短路徑的那個並且確定最短，直到所有點路徑確定最短為止。
簡單的概括流程為：
- 一般從選定點開始拋入優先隊列。（路徑一般為0），
boolean數組標記0的位置(最短為0) , 然後0周圍連通的點拋入優先隊列中（可能是node類），並把各個點的距離記錄到對應數組內(如果小於就更新，大於就不動，初始第一次是無窮肯定會更新)，第一次就結束了 - 從隊列中拋出
距離最近的那個點B（第一次就是0周圍鄰居）。這個點距離一定是最近的（所有權值都是正的，點的距離只能越來越長。）標記這個點為true，並且將這個點的鄰居加入隊列(下一次確定的最短點在前面未確定和這個點鄰居中產生),並更新通過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; } Queue<node>q1=new PriorityQueue<node>(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;i<map[index].length;i++) { if(map[index][i]>0&&!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 Comparator<node>com=new Comparator<node>() { 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; } }
