戴克斯特拉(Dijkstra )算法介绍一种典型的最短路径算法——戴克斯特拉(Dijkstra )算法，并用于计算从一个节点到另一个节点的最短路径。 其主要特征是以起点为中心向外侧扩展层。 (广度优先搜索思想)延伸到终点。
最短路径问题是图论研究中的一个典型算法问题，旨在寻找图(由节点和路径组成)中两个节点之间的最短路径。 大致分为以下问题，但无论如何分类问题，本质思想都不会改变。 即，求出两点间的最短距离。
a )起点最短路径问题(即已知起点节点并求出最短路径的问题)。
b )决定终点的最短路径问题-与决定起点的问题相反，这个问题是知道终端节点并求出最短路径的问题。 在有向图中，这个问题与决定起点的问题完全相同，在有向图中，这个问题与决定反转所有路径方向的起点的问题相同。
c )知道起点终点的最短路径问题即起点和终点，求出两个节点之间的最短路径。
d )全局最短路径问题-求图中所有最短路径。
戴克斯特拉(Dijkstra )算法综述
如上图所示，抖动算法的中心思想如下。
指定节点。 例如，计算从“a”到其他节点的最短路径
引入三个集合(dis，already_arr，pre_visited )，dis集合包含所求出的最短路径的点(及其对应的最短长度)，already_arr记录各顶点是否被访问过
初始化三个集合。 already_arr集合被初始化，以便只有当前节点被设置为已访问。 即，设置为already_arr[index]=1
dis集合初始时为A-A=0 A-B=4、A-C=、A-D=2、A-E=
在尚未访问的节点中找到路径最短的点，并加入dis集合。 例如，A-D=2
更新already_arr和pre_visited的集合路径，if(d到b、c、e的距离(ad距离) a到b、c、e的距离)更新already_arr和pre_visited的集合
执行循环4和循环5两个步骤，直到遍历结束并获得从a到其他节点的最短路径
戴克斯特拉的算法应用场景——最短路径问题
战争时期，胜利乡有7个村庄(a、b、c、d、e、f、g ) )，现在有6个邮递员。 从g点出发，需要分别向a、b、c、d、e、f六个村子寄送邮件
各村庄的距离用分界线表示，例如ab相距5公里
问：怎么计算g村到其他村的最短距离？
从其他点到各点的最短距离是多少？
代码实现publicclassDijkstraalgorithm(/)表示与public static final int INF=65535无关； publicstaticvoidmain (字符串[ ] args ) { char[] vertexs={'A '、' b '、' c '、' d '、' e '、' f '、' G'}； int [ ] [ ]矩阵=new int [ vertexs.length ] [ vertexs.length ]； matrix[0]=new int[]{INF，5，7，INF，INF，INF，2}； matrix[1]=new int[]{5，INF，INF，9，INF，INF，3}； 矩阵[2]=new int [ ] { 7，INF，INF，INF，8，INF，INF}； matrix[3]=new int[]{INF，9，INF，INF，INF，4，INF}； matrix[4]=new int[]{INF，INF，8，INF，INF，5，4 }； matrix[5]=new int[]{INF，INF，INF，4，5，INF，6}； 矩阵[6]=new int [ ] { 2，3，INF，INF，4，6，INF}； 图形对象创建图形图形=新图形(顶点，矩阵)； graph.showGraph (； //开始查找的顶点的下标int index=6； graph.Dijkstra(index )； graph.showDijkstra(index )； } class graph { privatefinalchar [ ] vertex； //顶点数组私有final int [ ] [ ]矩阵； //相邻矩阵私有可见vert
ex vv; // 已访问顶点集合 // 构造器 public Graph(char[] vertex, int[][] matrix) { this.vertex = vertex; this.matrix = matrix; } // 显示结果 public void showDijkstra(int index) { vv.print(index); } // 显示图 public void showGraph() { for (int[] link : this.matrix) { System.out.println(Arrays.toString(link)); } } // dijkstra 算法 public void dijkstra(int index) { vv = new VistedVertex(vertex.length, index); // 更新 index 下标顶点到周围顶点的距离和周围顶点的前驱顶点 update(index); for (int j = 1; j < vertex.length; j++) { // 选择并返回新的访问顶点 index = vv.updateArr(); // 更新 index 下标顶点到周围顶点的距离和周围顶点的前驱顶点 update(index); } } // 更新 index 下标顶点到周围顶点的距离和周围顶点的前驱顶点 public void update(int index) { int len; for (int i = 0; i < matrix[index].length; i++) { // len 含义是 : 出发顶点到 index 顶点的距离 + 从 index 顶点到 i 顶点的距离的和 len = vv.getDis(index) + matrix[index][i]; // 如果 i 顶点没有被访问过，并且 len 小于出发顶点到 i 顶点的距离，就需要更新 if (!vv.in(i) && len < vv.getDis(i)) { vv.updatePre(i, index);//更新 i 顶点的前驱为 index 顶点 vv.updateDis(i, len);//更新出发顶点到 i 顶点的距离 } } }}// 已访问顶点集合class VistedVertex { // 记录各个顶点是否被访问过 (1 表示访问过,0 未访问)会动态更新 public int[] already_arr; // 每个下标对应的值为前一个顶点下标, 会动态更新 public int[] pre_visited; // 记录出发顶点到其他所有顶点的距离,比如 G 为出发顶点，就会记录 G 到其它顶点的距离 // 会动态更新，求的最短距离就会存放到 dis public int[] dis; /** * 构造器 * @param length 顶点的个数 * @param index 出发顶点对应的下标 eg: G -> 6 */ public VistedVertex(int length, int index) { this.already_arr = new int[length]; this.pre_visited = new int[length]; this.dis = new int[length]; // 初始化 dis 数组 Arrays.fill(dis, DijkstraAlgorithm.INF); // 设置出发顶点已被访问过 this.already_arr[index] = 1; // 设置出发顶点的访问距离为 0 this.dis[index] = 0; } /** * 判断 index 顶点是否被访问过 * @param index 顶点对应的下标 * @return 若访问过就返回true，否则返回false */ public boolean in(int index) { return already_arr[index] == 1; } /** * 更新出发顶点到 index 顶点之间的距离 * @param index 顶点对应的下标 * @param len 距离 */ public void updateDis(int index, int len) { this.dis[index] = len; } /** * 更新 pre 顶点的前驱为 index 顶点 * @param pre 当前前驱顶点对应的下标 * @param index 要更新的前驱顶点对应的下标 */ public void updatePre(int pre, int index) { this.pre_visited[pre] = index; } // 返回出发顶点到 index 顶点之间的距离 public int getDis(int index) { return this.dis[index]; } // 继续选择并返回新的访问顶点 // 比如这里的 G 完后，就是 A 点作为新的访问顶点(注意不是出发顶点) public int updateArr() { int min = DijkstraAlgorithm.INF; int index = 0; for (int i = 0; i < already_arr.length; i++) { if (already_arr[i] == 0 && dis[i] < min) { min = dis[i]; index = i; } } // 更新 index 顶点已被访问过 already_arr[index] = 1; return index; } // 打印最后的结果 public void print(int index) { System.out.println("nalready_arr=========================="); for (int i : already_arr) { System.out.print(i + " "); } System.out.println("npre_visited=========================="); for (int i : pre_visited) { System.out.print(i + " "); } System.out.println("ndis=================================="); for (int i : dis) { System.out.print(i + " "); } System.out.println(); char[] vertexs = {'A','B','C','D','E','F','G'}; int count = 0; for (int i : dis) { if (i != DijkstraAlgorithm.INF) { System.out.print(vertexs[index] + "->" + vertexs[count] + "的距离：" + i + "t"); } else { System.out.println("INF"); } count++; } }} 运行结果 从G点开始 从A点开始 从B点开始注：以上大部分内容来源于jwdbb老师的数据结构和算法笔记