1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135
| package com.atguigu.dijkstra;
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,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(2); 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)); } } public void dsj(int index) { vv = new VisitedVertex(vertex.length, 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); } } } }
class VisitedVertex { public int[] already_arr; public int[] pre_visited; public 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); this.already_arr[index] = 1; this.dis[index] = 0; } public boolean in(int index) { return already_arr[index] == 1; } public void updateDis(int index, int len) { dis[index] = len; } public void updatePre(int pre, int index) { pre_visited[pre] = 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("=========================="); for(int i : already_arr) { System.out.print(i + " "); } System.out.println(); for(int i : pre_visited) { System.out.print(i + " "); } System.out.println(); for(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++; } System.out.println(); } }
|