欧洲手表网站,长春自助建站系统,知名商业网站有哪些,石家庄市环保局网站建设项目备案系统迪杰斯特拉算法
介绍
迪杰斯特拉#xff08;Dijkstra#xff09;算法是典型最短路径算法#xff0c;用于计算一个节点到其他节点的最短路径。它的主要特点是以中心向外层层扩展#xff08;广度优先搜索思想#xff09;#xff0c;直到扩展到终点为止。
算法过程
设置…迪杰斯特拉算法
介绍
迪杰斯特拉Dijkstra算法是典型最短路径算法用于计算一个节点到其他节点的最短路径。它的主要特点是以中心向外层层扩展广度优先搜索思想直到扩展到终点为止。
算法过程
设置出发顶点为 v顶点集合 V{v1,v2,v3…vi}v 到 V 中各顶点的距离构成距离集合 DisDis{d1,d2,d3…di}Dis 集合记录着 v 到图中各顶点的距离到自身可以看做 0v 到 vi 举例对应为 di
从 Dis 中选择值最小的 di 并移出 Dis 集合同时移出 V 集合中对应的顶点 vi此时的 v 到 vi 即为最短路径更新 Dis 集合更新规则为比较 v 到 V 结合中顶点的距离值与 v 通过 vi 到 V 集合中顶点的距离值保留值最小的一个同时也应该更新顶点的前驱节点为 vi表明是通过 vi 到达的重复执行两步骤直到最短路径顶点为目标顶点即可结束
迪杰斯特拉算法最佳应用 - 最短路径 战争时期胜利乡有 7 个村庄A,B,C,D,E,F,G现在有六个邮差从 G 点出发需要分别把邮件分别送到 A,B,C,D,E,F 六个村庄各个村庄的距离用边线表示权比如 A - B 距离 5 公里问如何计算出 G 村庄到其他各个村庄的最短距离如果从其他点出发到各个点的最短距离又是多少
代码实现
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, 5, 7, N, N, N, 2};matrix[1] new int[]{5, N, N, 9, N, N, 3};matrix[2] new int[]{7, N, N, N, 8, N, N};matrix[3] new int[]{N, 9, N, N, N, 4, N};matrix[4] new int[]{N, N, 8, N, N, 5, 4};matrix[5] new int[]{N, N, N, 4, 5, N, 6};matrix[6] new int[]{2, 3, N, N, 4, 6, N};// 创建图Graph graph new Graph(vertex, matrix);graph.showGraph();graph.dsj(6);graph.showDijkstra();}
}class Graph {private char[] vertex; // 顶点数组private int[][] matrix; // 邻接矩阵private VisitedVertex vv; // 已经访问的顶点的集合public Graph(char[] vertex, int[][] matrix) {this.vertex vertex;this.matrix matrix;}/*** 显示结果*/public void showDijkstra() {vv.show();}/*** 显示图*/public void showGraph() {for (int[] link : matrix) {System.out.println(Arrays.toString(link));}}/*** 迪杰斯特拉算法** param index 表示出发顶点对应的下标*/public void dsj(int index) {vv new VisitedVertex(vertex.length, index);update(index); // 更新 index 顶点到周围顶点的距离和前驱顶点for (int j 1; j vertex.length; j) {index vv.updateArr(); // 选择并返回新的访问节点update(index); // 更新 index 顶点到周围顶点的距离和前驱顶点}}/*** 更新 index 下标顶点到周围顶点的距离和周围定额点的前驱顶点** param index*/private void update(int index) {int len 0;// 根据遍历我们的邻接矩阵的 matrix[index] 行for (int j 0; j matrix[index].length; j) {// len 含义是出发顶点到 index 顶点的距离 从 index 顶点到 j 顶点的距离的和len vv.getDis(index) matrix[index][j];// 如果 j 顶点没有被访问过并且 len 小于出发顶点到 j 顶点的距离就需要更新if (!vv.in(j) len vv.getDis(j)) {vv.updatePre(j, index); // 更新 j 顶点的前驱为 index 顶点vv.updateDis(j, len); // 更新出发顶点到 j 顶点的距离}}}
}// 已访问顶点集合
class VisitedVertex {// 记录各个顶点是否访问过 1 表示访问过0 表示未访问会动态更新private int[] already_arr;// 每个下标对应的值为前一个顶点下标会动态更新private int[] pre_visited;// 记录出发顶点到其他所有顶点的距离比如 G 为出发顶点就会记录 G 到其他顶点的距离会动态更新求的最短距离就会存放到 disprivate int[] dis;/*** 构造器初始化** param length 表示顶点的个数* param index 出发顶点对应的下标*/public VisitedVertex(int length, int index) {this.already_arr new int[length];this.pre_visited new int[length];this.dis new int[length];// 初始化 disArrays.fill(dis, 65535);this.already_arr[index] 1; // 设置出发顶点被访问过this.dis[index] 0; // 设置出发顶点的访问距离为 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) {dis[index] len;}/*** 更新 pre 顶点的前驱顶点为 index 顶点** param pre 要更新的顶点* param index 跟新顶点*/public void updatePre(int pre, int index) {pre_visited[pre] index;}/*** 返回出发顶点到 index 顶点的距离** param index 顶点*/public int getDis(int index) {return dis[index];}/*** 继续选择并返回新的访问顶点** return*/public int updateArr() {int min 65535, 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 show() {System.out.println();// 输出 already_arrfor (int i : already_arr) {System.out.print(i );}System.out.println();// 输出 pre_visitedfor (int i : pre_visited) {System.out.print(i );}System.out.println();// 输出 disfor (int i : dis) {System.out.print(i );}System.out.println();char[] vertex {A, B, C, D, E, F, G};int count 0;for (int i : dis) {if (i ! 65535) {System.out.print(vertex[count] ( i ) );} else {System.out.println(N );}count;}}
}
