您现在的位置是:首页 > 后台技术 > 数据结构与算法数据结构与算法
迪杰斯特拉算法(图文)
第十三双眼睛2023-10-23【数据结构与算法】人已围观
简介迪杰斯特拉算法
迪杰斯特拉算法
package com.xingchen.day017; import java.util.Arrays; public class Dijstra { 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,7,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.show(); } } class Graph { char[] vertex;//顶点数组 int[][] matrix;//临接矩阵 VisitedVertex vv; public Graph(char[] vertex,int[][] matrix) { this.vertex = vertex; this.matrix = matrix; } public void showGraph() { for (int[] link: matrix) { System.out.println(Arrays.toString(link)); } } //index表示出发顶点对应的下标 public void dsj(int index) { vv = new VisitedVertex(vertex.length, index); //更新index顶点到周围顶点的距离和前驱顶点 update(index); for (int j = 1;j<vertex.length; j++) { //选择并返回新的访问顶点 index = vv.updateArr(); update(index); } } private void update(int index) { int len = 0; for (int j = 0;j<matrix[index].length;j++) { len = vv.getDis(index) +matrix[index][j]; if (!vv.in(j) && len < vv.getDis(j)) { vv.updatePre(j,index); vv.updateDis(j,len); } } } public void show() { vv.show(); } } class VisitedVertex { private int[] already_arr; private int[] pre_visited; private int[] dis; public VisitedVertex(int length,int index) { this.already_arr = new int[length]; this.pre_visited = new int[length]; this.dis = new int[length]; Arrays.fill(dis, 65535); already_arr[index] = 1;//设置出发顶点已被访问 this.dis[index] = 0; } //判断index对应的顶点是否被访问过,如果访问过,就返回true,否则返回false public boolean in(int index) { return already_arr[index] == 1; } //更新出发顶点到index的距离 public void updateDis(int index, int len) { dis[index] = len; } //更新节点的前驱节点为index节点 public void updatePre(int pre, int index) { pre_visited[pre] = index; } //返回出发顶点到index的距离 public int getDis(int index) { return dis[index]; } 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; } } already_arr[index] = 1; return index; } public void show() { System.out.println("========"); System.out.println(Arrays.toString(already_arr)); System.out.println(Arrays.toString(pre_visited)); System.out.println(Arrays.toString(dis)); 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 ++; } System.out.println(); } } |
Tags:
很赞哦! ()
上一篇:克鲁斯卡尔算法(图文)
下一篇:弗洛伊德算法(图文)