最短路径算法——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 = 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];
}
/**
* 创建图的过程
*/
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;//记录下标
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;
//是否是到当前节点的最短路径
for (int i = 0; i < graph.getVertexSize() ; i++) {
if(!isgetPath[i]&&shortTablePath[i]<min){
k = i;
min = shortTablePath[i];
}
}
//标志k的位置当前是最短路径
isgetPath[k] =true;
// 判断当前节点到各个节点的当前最短路径
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];
}
}
//打印当前步骤(非必须)
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();
}
//打印到各个节点的最短路径
for (int i = 0; i < shortTablePath.length; i++) {
System.out.println("V0到V" + i + "最短路径为 " + shortTablePath[i]);
}
}
//打印当期那的邻接矩阵
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);
}
}
这个就是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。。。
