最短路徑算法——Dijkstra(迪傑斯特拉)
恩 好久沒有寫部落格了，雖然我知道這種算法的部落格基本很少有人看，但是我還是決定把他寫出來
Dijkstra算法屬于最短路徑的算法，他的本質就是 一個按照路徑長度遞增的次序産生的最短路徑算法，他的應用還是比較普遍的。
我們這邊那這個圖來說
假如說我們這裡要尋找從 v0 - v8 的最短路徑，我們首先要想Prim算法一樣，把圖轉為鄰接矩陣，入圖下所示
他這個圖表示的就是你一個點到另一個點的距離，比如V0到V1是1 到v2是5 到v3是無窮大 說明不到3 v4 ,5 ,6,7,8 同樣是不通的，v1到v2的距離是3 到v3的距離是7 ，就這樣一個規律
這個算法是這樣走的
- 預設一個空的數組 就是他的數組的長度(點的數量) 比如是 shortTablePath[],預設的值就是∞，他到所有點的距離都是無窮大，還要初始化一個boolean數組 isgetPath[] 來記錄目前的點是不是是最短的路徑，同時防止回環。
-
初始化到第一個點的距離是0 因為v0到v0的距離永遠是0（本身到本身）同時把
isgetPath[0]置為true
-
然後從v0開始循環 v0 到 v1加起來的距離小于shortTablePath[1] 是以v0 -> v1的最短距離就是 1，v0 -> v2 的距離是5，5+0<∞ 是以v0 -> v2 的最短距離就是5，因為後面都不通，是以還是∞，第一遍結束結果就是
shortTablePath = {0 1 5 ∞ ∞ ∞ ∞ ∞ ∞}
isgetPath={true,false,false,false,false,false,false,false}
-
循環上面的步驟,到v1時
shortTablePath={0 1 4 8 6 1000 1000 1000 1000 }
isgetPath = {true true false false false false false false false }
到V2時：
shortTablePath={0 1 4 8 5 11 1000 1000 1000 }
isgetPath= {true true true false false false false false false }
到V3時
shortTablePath={0 1 4 7 5 8 11 14 1000 }
isgetPath={true true true false true false false false false }
以後的步驟省略。。。
從上面看 我們可以大緻了解到這個算法的核心
尋找到到V8節點的最短距離， 那麼我找到V0到V1 V1到V2 V2到V3 。。。每個節點的最短的距離，那麼他們的和就是到V8的最短的距離
我們用代碼實作來看 先建立了一個Graph類 這個類主要是建構圖和擷取圖的一些屬性
public class Graph {
private int vertexSize;//頂點數量
public int getVertexSize() {
return vertexSize;
}
public void setVertexSize(int vertexSize) {
this.vertexSize = vertexSize;
}
private int [] vertexs;//頂點數組
private int[][] matrix;
public int[][] getMatrix() {
return matrix;
}
public void setMatrix(int[][] matrix) {
this.matrix = matrix;
}
public static final int MAX_WEIGHT = ;
private boolean [] isVisited;
public Graph(int vertextSize){
this.vertexSize = vertextSize;
matrix = new int[vertextSize][vertextSize];
vertexs = new int[vertextSize];
for(int i = ;i<vertextSize;i++){
vertexs[i] = i;
}
isVisited = new boolean[vertextSize];
}
/**
* 建立圖的過程
*/
public void createGraph(){
int [] a1 = new int[]{,,,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT};
int [] a2 = new int[]{,,,,,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT};
int [] a3 = new int[]{,,,MAX_WEIGHT,,,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT};
int [] a4 = new int[]{MAX_WEIGHT,,MAX_WEIGHT,,,MAX_WEIGHT,,MAX_WEIGHT,MAX_WEIGHT};
int [] a5 = new int[]{MAX_WEIGHT,,,,,,,,MAX_WEIGHT};
int [] a6 = new int[]{MAX_WEIGHT,MAX_WEIGHT,,MAX_WEIGHT,,,MAX_WEIGHT,,MAX_WEIGHT};
int [] a7 = new int[]{MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,,,MAX_WEIGHT,,,};
int [] a8 = new int[]{MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,,,,,};
int [] a9 = new int[]{MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,,,};
matrix[] = a1;
matrix[] = a2;
matrix[] = a3;
matrix[] = a4;
matrix[] = a5;
matrix[] = a6;
matrix[] = a7;
matrix[] = a8;
matrix[] = a9;
}
}
核心算法 Dijkstra.java
public class Dijkstra {
private final static int MAXVEX = ;
private final static int MAXWEIGHT = ;
private int shortTablePath[] = new int[MAXVEX]; //記錄的是V0到某訂單的最短路徑
public void shortestPathDijkstra(Graph graph){
int min;
int k = ;//記錄下标
boolean isgetPath[] = new boolean[MAXVEX];
//初始化shortTablePath
shortTablePath = graph.getMatrix()[];
shortTablePath[]=;
isgetPath[] = true;
for (int v = ;v<graph.getVertexSize();v++){
min = MAXWEIGHT;
//是否是到目前節點的最短路徑
for (int i = ; i < graph.getVertexSize() ; i++) {
if(!isgetPath[i]&&shortTablePath[i]<min){
k = i;
min = shortTablePath[i];
}
}
//标志k的位置目前是最短路徑
isgetPath[k] =true;
// 判斷目前節點到各個節點的目前最短路徑
for (int j = ; j < graph.getVertexSize(); j++) {
if(!isgetPath[j]&&(min+graph.getMatrix()[k][j])<shortTablePath[j]){
shortTablePath[j] = min+graph.getMatrix()[k][j];
}
}
//列印目前步驟(非必須)
for (int i = ; i < shortTablePath.length ; i++) {
System.out.print(shortTablePath[i]+" ");
}
System.out.println();
for (int i = ; i < isgetPath.length ; i++) {
System.out.print(isgetPath[i]+" ");
}
System.out.println();
System.out.println();
System.out.println();
}
//列印到各個節點的最短路徑
for (int i = ; i < shortTablePath.length; i++) {
System.out.println("V0到V" + i + "最短路徑為 " + shortTablePath[i]);
}
}
//列印當期那的鄰接矩陣
public void printGraph(Graph graph){
for (int i = ; i < graph.getVertexSize() ; i++) {
for (int j = ; j < graph.getMatrix()[i].length; j++) {
if(graph.getMatrix()[i][j]<Graph.MAX_WEIGHT) {
System.out.print(graph.getMatrix()[i][j] + " ");
}else {
System.out.print("∞" + " ");
}
}
System.out.println();
}
}
public static void main(String[] args) {
Graph graph = new Graph(MAXVEX);
graph.createGraph();
Dijkstra dijkstra = new Dijkstra();
dijkstra.printGraph(graph);
dijkstra.shortestPathDijkstra(graph);
}
}
這個就是Dijkstra算法，跑起來~
V0到V0最短路徑為 0
V0到V1最短路徑為 1
V0到V2最短路徑為 4
V0到V3最短路徑為 7
V0到V4最短路徑為 5
V0到V5最短路徑為 8
V0到V6最短路徑為 10
V0到V7最短路徑為 12
V0到V8最短路徑為 16
nice。。。