1. 應(yīng)用場(chǎng)景：

假如有七個(gè)村莊(ABCDEFG)，有個(gè)人從G點(diǎn)出發(fā)，到其他六個(gè)村莊的最短路徑分別是多少？到A、B、F、E只有一條路，沒得選，但是到C有兩條路，可以是2 + 7，也可以是8 + 4，到D點(diǎn)可以是3 + 9，也可以是6 + 4。圖上標(biāo)明了距離我們當(dāng)然一看就知道怎么選，那么如何能讓程序選擇最短的路徑呢？

迪杰斯特拉算法就是求最短路徑的經(jīng)典算法。它的主要思想就是以起始點(diǎn)向外層層擴(kuò)展，用廣度優(yōu)先的思想，直到擴(kuò)展到終點(diǎn)為止。

2. 算法步驟：

以上面的例子，從G開始處理，來講解這個(gè)過程：

• 首先我們會(huì)用一個(gè)數(shù)組或者集合來保存這7個(gè)頂點(diǎn)，如下：

String[] vertexs = {"A", "B", "C", "D", "E", "F", "G"};

• 其次，會(huì)有一個(gè)鄰接矩陣來表示各個(gè)頂點(diǎn)之間的距離，如下(N表示聯(lián)不通，可以用一個(gè)很大的數(shù)表示)：

  A  B  C  D  E  F  G
A{N, 5, 7 ,N, N, N, 2}
B{5, N, N ,9, N, N, 3}
C{7, N, N ,N, 8, N, N}
D{N, 9, N ,N, N, 4, N}
E{N, N, 8 ,N, N, 5, 4}
F{N, N, N ,4, 5, N, 6}
G{2, 3, N ,N, 4, 6, N}

• 接著創(chuàng)建一個(gè)數(shù)組already_arr，長度為頂點(diǎn)的個(gè)數(shù)。數(shù)組里面，0表示未訪問過該頂點(diǎn)，1表示訪問過該頂點(diǎn)。初始的時(shí)候其他都是0，G頂點(diǎn)的是1。

int[] already_arr = {0, 0, 0, 0, 0, 0, 1};

• 再創(chuàng)建一個(gè)數(shù)組dis，長度也是頂點(diǎn)的個(gè)數(shù)。該數(shù)組記錄的是當(dāng)前頂點(diǎn)到其他頂點(diǎn)的距離，初始的時(shí)候是一個(gè)較大的數(shù)，到自己的距離就是0。

int[] dis = {N, N, N, N, N, N, 0};

• 還要?jiǎng)?chuàng)建一個(gè)數(shù)組pre_visited，長度也是頂點(diǎn)的個(gè)數(shù)。數(shù)組表示頂點(diǎn)的到前驅(qū)頂點(diǎn)的距離，初始時(shí)候都是0。

int[] pre_visited = {0, 0, 0, 0, 0, 0, 0};

• 處理了頂點(diǎn)G，即鄰接矩陣的最后一行，可以發(fā)現(xiàn)，G到A的距離是2，小于9999，到B的距離是3，也小于9999……所以更新dis數(shù)組，如下：

int[] dis = {2, 3, N, N, 4, 6, 0};

• 從鄰接矩陣的最后一行可以看出，G和A、B、E、F是直接連通的，也就說明，ABEF這四個(gè)點(diǎn)的前驅(qū)頂點(diǎn)都是G，所以pre_visited數(shù)組變成了：

int[] pre_visited = {6, 6, 0, 0, 6, 6, 0};

• 上面就是第一次的處理過程，然后按照廣度優(yōu)先的方式，每訪問一個(gè)頂點(diǎn)，就按照上面的方式去修改這3個(gè)數(shù)組。最后的G頂點(diǎn)到每個(gè)頂點(diǎn)的最短距離就記錄中dis數(shù)組中。

3. 代碼實(shí)現(xiàn)：

• 首先得把圖創(chuàng)建出來：

class Graph{
 String[] vertexs; // 存放頂點(diǎn)
 int[][] edges; // 鄰接矩陣，存放邊
 
 public Graph(String[] vertexs, int[][] edges) {
  this.vertexs = vertexs;
  this.edges = edges;
 }
}

• 然后，創(chuàng)建一個(gè)類，類里面有個(gè)三個(gè)屬性，就是上面說的那三個(gè)數(shù)組，以及一些必要的方法：

class VisitedVertex{
 
 private static final int N = 999;
 
 public int[] already_arr;
 public int[] pre_visited;
 public int[] dis;
 
 /**
  * 構(gòu)造器
  * @param length 頂點(diǎn)的個(gè)數(shù)
  * @param index 出發(fā)點(diǎn)的索引
  */
 public VisitedVertex(int length, int index) {
  this.already_arr = new int[length];
  this.pre_visited = new int[length];
  this.dis = new int[length];
  // 初始化dis數(shù)組
  Arrays.fill(dis, N);
  dis[index] = 0;
 }
 
 /**
  * 判斷index對(duì)應(yīng)的頂點(diǎn)是否被訪問過
  * @param index
  * @return
  */
 public boolean isVisited(int index) {
  return already_arr[index] == 1;
 }
 
 /**
  * 更新dis數(shù)組，索引為index的值更新為len
  * @param index
  * @param len
  */
 public void updateDis(int index, int len) {
  dis[index] = len;
 }
 
 /**
  * 更新前驅(qū)頂點(diǎn)
  * @param index
  * @param val
  */
 public void updatePre(int index, int val) {
  pre_visited[index] = val;
 }
 
/**
  * 將index設(shè)置為已訪問
  * @param index
  */
 public void updateAlreadyArr(int index) {
  already_arr[index] = 1;
 }

 /**
  * 返回出發(fā)頂點(diǎn)到index這個(gè)頂點(diǎn)的距離
  * @param index
  * @return
  */
 public int getDis(int index) {
  return dis[index];
 }

    /**
  * 返回要處理的下一個(gè)頂點(diǎn)
  * @return
  */
 public int nextVertexs() {
  int index = 0;
  int min = N;
  for (int i=0; i< already_arr.length; i++) {
   if (!isVisited(i) && dis[i] < min) {
    min = dis[i];
    index = i;
   }
  }
  updateAlreadyArr(index);
  return index;
 }
 
 public void printArr() {
  System.out.println(Arrays.toString(this.dis) + "   dis");
  System.out.println(Arrays.toString(this.pre_visited) + "   pre_visited");
  System.out.println(Arrays.toString(this.already_arr) + "   already_arr");
 }
}

• 那么接下來就可以在Graph類中新增一個(gè)方法，來實(shí)現(xiàn)迪杰斯特拉算法了，如下：

    /**
  * 迪杰斯特拉算法實(shí)現(xiàn)
  * @param index 出發(fā)頂點(diǎn)的下標(biāo)
  */
 public void dsj(int index) {
  VisitedVertex visitedVertex = new VisitedVertex(this.vertexs.length, index);
  updateArrs(index, visitedVertex);
  // 下一個(gè)要處理的頂點(diǎn)
  for (int i=1; i<vertexs.length; i++) {
   index = visitedVertex.nextVertexs();
   updateArrs(index, visitedVertex);
  }
  visitedVertex.printArr();
 }
 
 /**
  * 拿到鄰接矩陣的第index行，根據(jù)這一行對(duì)三個(gè)數(shù)組進(jìn)行更新
  * @param index
  * @param visitedVertex
  */
 private void updateArrs(int index, VisitedVertex visitedVertex) {
  int[] tempArr = this.edges[index];
  // distance表示出發(fā)頂點(diǎn)到索引為index的這個(gè)頂點(diǎn)的距離
  int distance = 0;
  for (int i=0; i< tempArr.length; i++) {
      // 先前的距離 + 本次遍歷得到的距離
   distance = visitedVertex.getDis(index) + tempArr[i];
   if (distance < visitedVertex.getDis(i) && !visitedVertex.isVisited(i)) {
    visitedVertex.updateDis(i, distance);
    visitedVertex.updatePre(i, index);
    visitedVertex.updateAlreadyArr(index);
   }
  }
 }

測(cè)試方法：

public class DijkstraDemo {
 
 public static final int N = 999;

 public static void main(String[] args) {
  String[] vertexs = {"A", "B", "C", "D", "E", "F", "G"};
  int[][] edges = {
   {N, 5, 7 ,N, N, N, 2},
   {5, N, N ,9, N, N, 3},
   {7, N, N ,N, 8, N, N},
   {N, 9, N ,N, N, 4, N},
   {N, N, 8 ,N, N, 5, 4},
   {N, N, N ,4, 5, N, 6},
   {2, 3, N ,N, 4, 6, N}
  };
  Graph graph = new Graph(vertexs, edges);
  graph.dsj(6);
 }
}

運(yùn)行后得到結(jié)果如下：

dis數(shù)組就是我們想要的結(jié)果，即對(duì)應(yīng)的頂點(diǎn)G到各個(gè)點(diǎn)的最短距離。