最短路徑算法——Dijkstra(迪杰斯特拉)
恩 好久沒有寫博客了，雖然我知道這種算法的博客基本很少有人看，但是我還是決定把他寫出來
Dijkstra算法屬于最短路徑的算法，他的本質(zhì)就是 一個(gè)按照路徑長度遞增的次序產(chǎn)生的最短路徑算法，他的應(yīng)用還是比較普遍的。
我們這邊那這個(gè)圖來說
假如說我們這里要尋找從 v0 - v8 的最短路徑，我們首先要想Prim算法一樣，把圖轉(zhuǎn)為鄰接矩陣，如圖下所示
他這個(gè)圖表示的就是你一個(gè)點(diǎn)到另一個(gè)點(diǎn)的距離，比如V0到V1是1 到v2是5 到v3是無窮大 說明不到3 v4 ,5 ,6,7,8 同樣是不通的，v1到v2的距離是3 到v3的距離是7 ，就這樣一個(gè)規(guī)律
這個(gè)算法是這樣走的
默認(rèn)一個(gè)空的數(shù)組 就是他的數(shù)組的長度(點(diǎn)的數(shù)量) 比如是 shortTablePath[],默認(rèn)的值就是∞，他到所有點(diǎn)的距離都是無窮大，還要初始化一個(gè)boolean數(shù)組 isgetPath[] 來記錄當(dāng)前的點(diǎn)是不是是最短的路徑，同時(shí)防止回環(huán)。
-
初始化到第一個(gè)點(diǎn)的距離是0 因?yàn)関0到v0的距離永遠(yuǎn)是0（本身到本身）同時(shí)把
isgetPath[0]置為true
-
然后從v0開始循環(huán) v0 到 v1加起來的距離小于shortTablePath[1] 所以v0 -> v1的最短距離就是 1，v0 -> v2 的距離是5，5+0<∞ 所以v0 -> v2 的最短距離就是5，因?yàn)楹竺娑疾煌?，所以還是∞，第一遍結(jié)束結(jié)果就是
shortTablePath = {0 1 5 ∞ ∞ ∞ ∞ ∞ ∞}
isgetPath={true,false,false,false,false,false,false,false}
-
循環(huán)上面的步驟,到v1時(shí)
shortTablePath={0 1 4 8 6 1000 1000 1000 1000 }
isgetPath = {true true false false false false false false false }
到V2時(shí)：
shortTablePath={0 1 4 8 5 11 1000 1000 1000 }
isgetPath= {true true true false false false false false false }
到V3時(shí)
shortTablePath={0 1 4 7 5 8 11 14 1000 }
isgetPath={true true true false true false false false false }
以后的步驟省略。。。
從上面看 我們可以大致理解到這個(gè)算法的核心
尋找到到V8節(jié)點(diǎn)的最短距離， 那么我找到V0到V1 V1到V2 V2到V3 。。。每個(gè)節(jié)點(diǎn)的最短的距離，那么他們的和就是到V8的最短的距離
我們用代碼實(shí)現(xiàn)來看 先建立了一個(gè)Graph類 這個(gè)類主要是構(gòu)建圖和獲取圖的一些屬性
public class Graph {
private int vertexSize;//頂點(diǎn)數(shù)量
public int getVertexSize() {
return vertexSize;
}
public void setVertexSize(int vertexSize) {
this.vertexSize = vertexSize;
}
private int [] vertexs;//頂點(diǎn)數(shù)組
private int[][] matrix;
public int[][] getMatrix() {
return matrix;
}
public void setMatrix(int[][] matrix) {
this.matrix = matrix;
}
public static final int MAX_WEIGHT = 1000;
private boolean [] isVisited;
public Graph(int vertextSize){
this.vertexSize = vertextSize;
matrix = new int[vertextSize][vertextSize];
vertexs = new int[vertextSize];
for(int i = 0;i<vertextSize;i++){
vertexs[i] = i;
}
isVisited = new boolean[vertextSize];
}
/**
* 創(chuàng)建圖的過程
*/
public void createGraph(){
int [] a1 = new int[]{0,1,5,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT};
int [] a2 = new int[]{1,0,3,7,5,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT};
int [] a3 = new int[]{5,3,0,MAX_WEIGHT,1,7,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT};
int [] a4 = new int[]{MAX_WEIGHT,7,MAX_WEIGHT,0,2,MAX_WEIGHT,3,MAX_WEIGHT,MAX_WEIGHT};
int [] a5 = new int[]{MAX_WEIGHT,5,1,2,0,3,6,9,MAX_WEIGHT};
int [] a6 = new int[]{MAX_WEIGHT,MAX_WEIGHT,7,MAX_WEIGHT,3,0,MAX_WEIGHT,5,MAX_WEIGHT};
int [] a7 = new int[]{MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,3,6,MAX_WEIGHT,0,2,7};
int [] a8 = new int[]{MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,9,5,2,0,4};
int [] a9 = new int[]{MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,7,4,0};
matrix[0] = a1;
matrix[1] = a2;
matrix[2] = a3;
matrix[3] = a4;
matrix[4] = a5;
matrix[5] = a6;
matrix[6] = a7;
matrix[7] = a8;
matrix[8] = a9;
}
}
核心算法 Dijkstra.java
public class Dijkstra {
private final static int MAXVEX = 9;
private final static int MAXWEIGHT = 1000;
private int shortTablePath[] = new int[MAXVEX]; //記錄的是V0到某訂單的最短路徑
public void shortestPathDijkstra(Graph graph){
int min;
int k = 0;//記錄下標(biāo)
boolean isgetPath[] = new boolean[MAXVEX];
//初始化shortTablePath
shortTablePath = graph.getMatrix()[0];
shortTablePath[0]=0;
isgetPath[0] = true;
for (int v = 1 ;v<graph.getVertexSize();v++){
min = MAXWEIGHT;
//是否是到當(dāng)前節(jié)點(diǎn)的最短路徑
for (int i = 0; i < graph.getVertexSize() ; i++) {
if(!isgetPath[i]&&shortTablePath[i]<min){
k = i;
min = shortTablePath[i];
}
}
//標(biāo)志k的位置當(dāng)前是最短路徑
isgetPath[k] =true;
// 判斷當(dāng)前節(jié)點(diǎn)到各個(gè)節(jié)點(diǎn)的當(dāng)前最短路徑
for (int j = 0; j < graph.getVertexSize(); j++) {
if(!isgetPath[j]&&(min+graph.getMatrix()[k][j])<shortTablePath[j]){
shortTablePath[j] = min+graph.getMatrix()[k][j];
}
}
//打印當(dāng)前步驟(非必須)
for (int i = 0; i < shortTablePath.length ; i++) {
System.out.print(shortTablePath[i]+" ");
}
System.out.println();
for (int i = 0; i < isgetPath.length ; i++) {
System.out.print(isgetPath[i]+" ");
}
System.out.println();
System.out.println();
System.out.println();
}
//打印到各個(gè)節(jié)點(diǎn)的最短路徑
for (int i = 0; i < shortTablePath.length; i++) {
System.out.println("V0到V" + i + "最短路徑為 " + shortTablePath[i]);
}
}
//打印當(dāng)期那的鄰接矩陣
public void printGraph(Graph graph){
for (int i = 0; i < graph.getVertexSize() ; i++) {
for (int j = 0; 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);
}
}
這個(gè)就是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。。。
