当前位置 博文首页 > Inmaturity_7的博客：迪杰斯特拉(Dijkstra)算法学习(Java)
学习视频：尚硅谷韩老师java讲解数据结构和算法
迪杰斯特拉(Dijkstra)算法是典型最短路径算法，用于计算一个结点到其他结点的最短路径。它的主要特点是以 起始点为中心向外层层扩展**(广度优先搜索思想)**，直到扩展到终点为止。
package com.lxf.dijstra;
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 graph = new Graph(vertex, matrix);
//测试，看看图的邻接矩阵是否ok
graph.showGraph();
//测试迪杰斯特拉算法
graph.dsj(6);
graph.show();
}
}
/**
*
*/
// 已访问顶点集合
class VisitedVertex {
// 记录各个顶点是否访问过,true:表示访问过,false:未访问,会动态更新
public boolean[] already_arr;
// 每个下标对应的值为前一个顶点下标, 会动态更新
public int[] pre_visited;
// 记录出发顶点到其他所有顶点的距离,比如 G 为出发顶点，就会记录 G 到其它顶点的距离，会动态更新，求 的最短距离就会存放到 dis
public int[] dis;
/**
* 构造器
* @param length ：表示顶点的个数
* @param index： 出发顶点对应的下标，比如G顶点，下标就是6
*/
public VisitedVertex(int length,int index) {
this.already_arr=new boolean[length];
this.pre_visited=new int[length];
this.dis=new int[length];
//初始化dis数组
Arrays.fill(dis,65535);
dis[index]=0;//设置出发顶点本身下标为0
this.already_arr[index]=true;//设置出发顶点为已访问过
}
/**
* 功能：更新出法顶点到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];
}
/**
* 继续选择并返回新的访问顶点，比如这里的G顶点后，就是将A点作为新的访问顶点（注意不是出发点）
* @return
*/
public int updateArr(){
int min=65535,index=0;
for (int i = 0; i < already_arr.length; i++) {
if(!already_arr[i]&&dis[i]<min){
min=dis[i];
index=i;
}
}
//更新index 顶点被访问过
already_arr[index]=true;
return index;
}
/**
* 显示最后的结果
* 即将三个数组的情况输出
*/
public void show(){
System.out.println("===================================");
//输出already_arr
for (boolean b : already_arr) {
System.out.print(b+" ");
}
System.out.println();
//输出pre_visited
for (int i : pre_visited) {
System.out.print(i+" ");
}
System.out.println();
//输出dis
for (int i : dis) {
System.out.print(i+" ");
}
System.out.println();
}
}
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 showGraph(){
for (int[] link : matrix) {
System.out.println(Arrays.toString(link));
}
}
/**
* 迪杰斯特拉算法
* @param index
*/
public void dsj(int index){
vv = new VisitedVertex(vertex.length, index);
//更新index顶点到周围顶点的距离和前驱结点
update(index);
for (int i = 0; i < vertex.length; i++) {
index=vv.updateArr();//选择并返回新的访问顶点
update(index);//更新index顶点到周围顶点的距离和前驱结点
}
}
/**
* 更新index下标顶点到周围顶点的距离和周围顶点的前驱顶点
* @param index
*/
private void update(int index){
// 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};
int len=0;
//根据遍历我们的邻接矩阵的matrix[index]行
for (int i =
