Dijkstra算法实现（java）

一、Dijkstra算法介绍

  Dijkstra（迪杰斯特拉）算法是求解单源最短路径的经典算法，其原理也是基于贪心策略的。

二、Dijkstra算法原理

  Dijkstra算法设置一个集合 S S S记录已求得的最短路径的顶点，初始时把源点 v 0 v_{0} v0​放入 S S S，集合 S S S每并入一个新顶点 v i v_{i} vi​，都要修改源点 v 0 v_{0} v0​到集合 V − S V-S V−S中顶点当前的最短路径长度值。
  在构造的过程中还设置了两个辅助数组：

（1）dist[]：记录从源点 v 0 v_{0} v0​到其他各顶点当前的最短路径长度，它的初态为:若从 v 0 v_{0} v0​到 v i v_{i} vi​有弧，则dist[i]为弧上的权值；否则置dist[i]为 ∞ ∞ ∞。
（2）path[]: path[i]表示从源点到顶点i之间的最短路径的前驱结点。在算法结束时，可根据其值追溯得到源点 v 0 v_{0} v0​到顶点 v i v_{i} vi​的最短路径。

  假设从顶点0出发，即 v 0 = 0 v_{0}=0 v0​=0，集合 S S S最初只包含顶点0，邻接矩阵arcs表示带权有向图，若不存在有向边，则arcs [i][j]为arcs[i][j]表示有向边的权值 ∞ ∞ ∞。
  Dijkstra算法的步骤如下（不考虑对path[]的操作):

1）初始化：集合S初始为{0}，dist[]的初始值dist[i]=arcs[0][i];i=1,2,…,n-1。
2）从顶点集合V-S中选出 v j v_{j} vj​，满足dist[j]=Min {dist[i]}， v i ∈ V − S v_{i} in V-S vi​∈V−S， v j v_{j} vj​就是当前求得的一条从 v 0 v_{0} v0​出发的最短路径的终点，令 S = S ∪ j S=Scup {j} S=S∪j。
3）修改从 v 0 v_{0} v0​出发到集合V-S上任一顶点 v k v_{k} vk​可达的最短路径长度：若dist[j]+arcs[j][k] 4）重复2）~3）操作共n-1次，直到所有的顶点都包含在S中。

步骤3），每当一个顶点加入S后，可能需要修改源点 v 0 v_{0} v0​到集合V-S中可达顶点当前的最短路径长度，下面举一简单例子证明。如下图所示，源点为 v 0 v_{0} v0​,初始时S={ v 0 v_{0} v0​},dist[1]=4，dist[2]=8，当将 v 1 v_{1} v1​并入集合S后，dist[2]需要更新为6。

三、Dijkstra算法示例 顶点第1轮第2轮第3轮第4轮210（ v 1 v_{1} v1​-> v 2 v_{2} v2​）8（ v 1 v_{1} v1​-> v 5 v_{5} v5​-> v 2 v_{2} v2​）8（ v 1 v_{1} v1​-> v 5 v_{5} v5​-> v 2 v_{2} v2​）3 ∞ ∞ ∞14（ v 1 v_{1} v1​-> v 5 v_{5} v5​-> v 3 v_{3} v3​）13（ v 1 v_{1} v1​-> v 5 v_{5} v5​-> v 4 v_{4} v4​-> v 3 v_{3} v3​）9（ v 1 v_{1} v1​-> v 5 v_{5} v5​-> v 2 v_{2} v2​-> v 3 v_{3} v3​）4 ∞ ∞ ∞ 7（ v 1 v_{1} v1​-> v 5 v_{5} v5​-> v 4 v_{4} v4​）55（ v 1 v_{1} v1​-> v 5 v_{5} v5​）集合S{1，5}{1，5，4}{1，5，4，2}{1，5，4，2，3}

  从顶点1开始，每次将最短路径的顶点加入集合，根据集合中已有是的顶点，寻找到各个顶点的最短路径。

四、代码实现

package com.haiyang.algorithm.dijkstra;import com.sun.corba.se.impl.orbutil.graph.Graph;import java.util.Arrays;public class DijkstraAlgorithm { public static void main(String[] args) { char[] vertex = {'A', 'B', 'C', 'D', 'E', 'F', 'G'}; //邻接矩阵 int[][] matrix = new int[vertex.length][vertex.length]; final int N = 65535;// 表示不可以连接 matrix[0] = new int[]{N, 10, N, N, 5}; matrix[1] = new int[]{N, N, 1, N, 2}; matrix[2] = new int[]{N, N, N, 4, N}; matrix[3] = new int[]{7, N, 6, N, N}; matrix[4] = new int[]{N, 3, 9, 2, N}; //创建 Graph对象 DGraph graph = new DGraph(vertex, matrix); //测试, 看看图的邻接矩阵是否ok graph.showGraph(); //测试迪杰斯特拉算法 graph.dijkstra(0); graph.showDijkstra('A', 'C'); }}//已访问顶点集合class VisitedVertex { //记录各个顶点是否访问，1表示访问过，0表示未访问过 public int[] alreadyVertex; //表示从源点到顶点i之间的最短路径的前驱结点 public int[] path; //记录从源点到其他各个顶点当前的最短路径长度 public int[] dist; public VisitedVertex(int vertexNum, int vertexIndex) { this.alreadyVertex = new int[vertexNum]; this.path = new int[vertexNum]; this.dist = new int[vertexNum]; //初始化dist数组，顶点i到其他顶点的距离初始为65536，到自己的距离初始为0。 Arrays.fill(dist, 65535); dist[vertexIndex] = 0; //初始顶点已访问 this.alreadyVertex[vertexIndex] = 1; } public boolean isVisited(int vertexIndex) { return alreadyVertex[vertexIndex] == 1; } public void updateDist(int objectiveVertexIndex, int objectiveVertexLength) { dist[objectiveVertexIndex] = objectiveVertexLength; } public void updatePath(int VertexIndex, int preVertexIndex) { path[VertexIndex] = preVertexIndex; } public int getDist(int vertexIndex) { return dist[vertexIndex]; } public int updateArr() { int min = 65536, index = 0; for (int i = 0; i < alreadyVertex.length; i++) { if (alreadyVertex[i] == 0 && dist[i] < min) { min = dist[i]; index = i; } } alreadyVertex[index] = 1; return index; } public void show(char begin, char end) { System.out.println("==================="); int beginIndex = 0; int endIndex = 0; char[] vertex = {'A', 'B', 'C', 'D', 'E', 'F', 'G'}; for (int i = 0; i < vertex.length; i++) { if (vertex[i] == begin) { beginIndex = i; } if (vertex[i] == end) { endIndex = i; } } System.out.println(begin + " -> " + end + "的最短距离为：" + dist[endIndex]); System.out.print(begin + " -> " + end + "的最短路径为："); showPath(beginIndex, endIndex); System.out.println(vertex[endIndex]); } private void showPath(int beginIndex, int endIndex) { char[] vertex = {'A', 'B', 'C', 'D', 'E', 'F', 'G'}; if (path[endIndex] == beginIndex) { System.out.print(vertex[beginIndex] + " -> "); return; } else { showPath(beginIndex, path[endIndex]); } System.out.print(vertex[path[endIndex]] + " -> "); }}class DGraph { private char[] vertex;//顶点数组 private int[][] arcs;//邻接矩阵 private VisitedVertex visitedVertex; public DGraph(char[] vertex, int[][] arcs) { this.vertex = vertex; this.arcs = arcs; } public void showGraph() { for (int[] link : arcs) { System.out.println(Arrays.toString(link)); } } public void dijkstra(int index) { visitedVertex = new VisitedVertex(vertex.length, index); update(index); for (int i = 1; i < vertex.length; i++) { index = visitedVertex.updateArr(); update(index); } } //更新index下标顶点到周围顶点的距离和周围顶点的前驱顶点 public void update(int index) { int len = 0; //根据邻接矩阵找到邻接顶点 for (int i = 0; i < arcs[index].length; i++) { //从出发顶点到index顶点的距离+ 从index顶点到i顶点的距离的和 len = visitedVertex.getDist(index) + arcs[index][i]; if (!visitedVertex.isVisited(i) && len < visitedVertex.getDist(i)) { visitedVertex.updatePath(i, index);//更新前驱顶点 visitedVertex.updateDist(i, len); //更新最短距离 } } } public void showDijkstra(char begin, char end) { visitedVertex.show(begin, end); }}