介紹

對于 dijkstra 算法，很多人可能感覺熟悉而又陌生，可能大部分人比較了解 bfs和dfs ，而對dijkstra和floyd算法可能知道大概是圖論中的某個算法，但是可能不清楚其中的作用和原理，又或許，你曾經感覺它很難，那么，這個時候正適合你重新認識它。

Dijkstra能是干啥的？

Dijkstra是用來求單源最短路徑的

就拿上圖來說，假如直到的路徑和長度已知，那么可以使用 dijkstra 算法計算 南京到圖中所有節點的最短距離。

單源什么意思？

• 從一個頂點出發，Dijkstra算法只能求一個頂點到其他點的最短距離而不能任意兩點。

和 bfs 求的最短路徑有什么區別？

• bfs 求的與其說是路徑，不如說是 次數 。因為bfs他是按照隊列一次一次進行加入相鄰的點，而兩點之間沒有權值或者權值相等(代價相同)。處理的更多是偏向迷宮類的這種都是只能走鄰居(不排除特例)。

Dijkstra在處理具體實例的應用還是很多的，因為具體的問題其實帶權更多一些。

比如一個城市有多個鄉鎮，鄉鎮可能有道路，也可能沒有，整個鄉鎮聯通，如果想計算每個鄉鎮到ａ鎮的最短路徑，那么Dijkstra就派上了用場。

算法分析

對于一個算法，首先要理解它的 運行流程 。

對于一個Dijkstra算法而言，前提是它的前提條件和環境：

• 一個連通圖，若干節點，節點可能有數值，但是 路徑 一定有 權值 。并且路徑 不能為負 。否則Dijkstra就不適用。

Dijkstra的核心思想是貪心算法的思想。不懂貪心？

貪心算法（又稱貪婪算法）是指，在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，他所做出的是在某種意義上的局部最優解。

貪心算法不是對所有問題都能得到整體最優解，關鍵是貪心策略的選擇，選擇的貪心策略必須具備無后效性，即某個狀態以前的過程不會影響以后的狀態，只與當前狀態有關。

對于貪心算法，在很多情況都能用到。下面舉幾個不恰當的例子！

打個比方，吃自助餐，目標是吃回本，那么胃有限那么每次都僅最貴的吃。

上學時，麻麻說只能帶5個蘋果，你想帶最多，那么選五個蘋果你每次都選最大的那個五次下來你就選的最重的那個。

不難發現上面的 策略 雖然沒有很強的理論數學依據 ，或者不太好說明。但是 事實規律就是那樣 ，并且對于貪心問題大部分都需要 排序 ,還可能會遇到類排序。并且一個物體可能有多個屬性，不同問題需要按照不同屬性進行排序，操作。

那么我們的 Dijkstra 是如何貪心的呢？對于一個點，求圖中所有點的最短路徑，如果沒有正確的方法胡亂想確實很難算出來，并且如果暴力匹配復雜度呈指數級上升不適合解決實際問題。

那么我們該怎么想呢？

Dijkstra算法的前提：

1. 首先，Dijkstra處理的是帶正權值的 有權圖 ，那么，就需要一個 二維數組 （如果空間大用list數組）存儲各個點到達( 邊 )的權值大小。 (鄰接矩陣或者鄰接表存儲)
2. 其次，還需要一個 boolean數組 判斷那些點已經確定最短長度，那些點沒有確定。 int數組 記錄距離( 在算法執行過程可能被多次更新 )。
3. 需要 優先隊列 加入 已經確定點的周圍點 。每次拋出確定最短路徑的那個并且確定最短，直到所有點路徑確定最短為止。

簡單的概括流程為：

• 一般從選定點開始拋入優先隊列。（路徑一般為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; 
 }
}

執行結果：

當然，dijkstra算法比較靈活，實現方式也可能有點區別，但是思想是不變的：一個貪心思路。dijkstra執行一次就能夠確定一個點，所以只需要執行點的總和次數即可完成整個算法。