描述

算法過程

代碼實現(xiàn)

package com.atguigu.dijkstra;import com.sun.xml.internal.fastinfoset.algorithm.BooleanEncodingAlgorithm;import javax.sound.midi.Soundbank; import java.util.Arrays; import java.util.TimerTask;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};//創(chuàng)建Graph對象Graph graph = new Graph(vertex, matrix);//測試看看圖的鄰接矩陣是否OKgraph.showGraph();//測試算法graph.dsj(2);//cgraph.showDijkstra();}}class Graph {private char[] vertex;//頂點數(shù)組private int[][] matrix;//鄰接矩陣private VisitedVertex vv;//已經(jīng)訪問的頂點集合//構(gòu)造器public Graph(char[] vertex, int[][] matrix) {this.vertex = vertex;this.matrix = matrix;}//顯示結(jié)果public void showDijkstra(){vv.show();}//顯示圖public void showGraph() {for (int[] link : matrix) {System.out.println(Arrays.toString(link));}}//迪杰斯特拉算法實現(xiàn)/**** @param index 表示出發(fā)頂點對應(yīng)的下標*/public void dsj(int index){vv = new VisitedVertex(vertex.length, index);update(index);//更新index頂點到周圍頂點的距離和前驅(qū)頂點for (int j = 1; j < vertex.length; j++) {index=vv.updateArr();//選擇并返回新的訪問頂點update(index);//更新index頂點到周圍頂點的距離和前驅(qū)頂點}}//更新index下標頂點到周圍頂點的距離和周圍頂點的前驅(qū)頂點private void update(int index){int len=0;//根據(jù)遍歷我們的鄰接矩陣的matrix[index].length行for (int j = 0; j < matrix[index].length; j++) {//len含義是：出發(fā)頂點到index頂點的距離+從index頂點到j(luò)頂點的距離的和len=vv.getDis(index)+matrix[index][j];//如果j頂點沒有被訪問過，并且len小于出發(fā)頂點到j(luò)頂點的距離，就需要更新if(!vv.in(j)&&len<vv.getDis(j)){vv.updatePre(j,index);//更新j頂點的前驅(qū)為index頂點vv.updateDis(j,len);//更新出發(fā)頂點到j(luò)頂點的距離}}}}// 已訪問頂點集合 class VisitedVertex {// 記錄各個頂點是否訪問過 1表示訪問過,0未訪問,會動態(tài)更新public int[] already_arr;// 每個下標對應(yīng)的值為前一個頂點下標, 會動態(tài)更新public int[] pre_visited;// 記錄出發(fā)頂點到其他所有頂點的距離,比如G為出發(fā)頂點，就會記錄G到其它頂點的距離，會動態(tài)更新，求的最短距離就會存放到dispublic int[] dis;//構(gòu)造器/***** @param length 表示頂點的個數(shù)* @param index 出發(fā)頂點對應(yīng)的下標，比如G頂點，下標是6*/public VisitedVertex(int length,int index){this.already_arr=new int[length];this.pre_visited=new int[length];this.dis=new int[length];//初始化dis數(shù)組Arrays.fill(dis,65535);this.already_arr[index]=1;//設(shè)置出發(fā)頂點被訪問過this.dis[index]=0;//是指出發(fā)頂點的訪問距離為0}/*** 判斷index頂點是否被訪問過* @param index* @return 如果訪問過，就返回true，否則返回false*/public boolean in(int index){return already_arr[index]==1;}/*** 更新出發(fā)頂點到index頂點的距離* @param index* @param len*/public void updateDis(int index,int len){dis[index]=len;}/*** 更新pre這個頂點的前驅(qū)為index的頂點* @param pre* @param index*/public void updatePre(int pre,int index){pre_visited[pre]=index;}/*** 返回出發(fā)頂點到index頂點的距離* @param index*/public int getDis(int index){return dis[index];}//繼續(xù)選擇并返回新的訪問頂點，比如這里的G完后，就是A點作為新的訪問頂點(注意不是新節(jié)點)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;}//顯示最后的結(jié)果//即將三個數(shù)組的情況輸出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++;}System.out.println();}}

總結(jié)

以上是生活随笔為你收集整理的迪杰斯特拉算法(最短路径)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。