迪杰斯特拉算法:使用图的广度优先遍历算法,比如先从G点出发,找到能与G直接连接的顶点,然后才从与G最近的A出发,找到与A相邻的节点。通过比较G到每个顶点的距离大小,筛选出到每个点的最短路径
代码:
/**
* 迪杰斯特拉算法球最短路径问题
*/
public class Dijkstra {
public static void main(String[] args) {
char[] vertexs = {'A','B','C','D','E','F','G'};
final int N = 65535;//N表示两点之间不直连
//邻接矩阵
int[][] weight = {
{N,5,7,N,N,N,2},
{5,N,N,9,N,N,3},
{7,N,N,N,8,N,N},
{N,9,N,N,N,4,N},
{N,N,8,N,N,5,4},
{N,N,N,4,5,N,6},
{2,3,N,N,4,6,N},
};
Graph graph = new Graph(vertexs, weight);
graph.print();
graph.dijkstra(6);
graph.show();
}
}
//图
class Graph{
private char[] vertexs;//顶点数组
private int[][] weight;//邻接矩阵
private VisitedVertex vv;
public Graph(char[] vertexs, int[][] weight) {
this.vertexs = vertexs;
this.weight = weight;
}
public void print(){
for(int[] link:weight){
System.out.println(Arrays.toString(link));
}
}
/**
* 迪杰斯特拉算法
* @param index 初始节点
*/
public void dijkstra(int index){
vv = new VisitedVertex(vertexs.length,index);
update(index);
for(int j = 1;j<vertexs.length;j++){//初始节点已经处理过了,所以需要处理vetexs.length - 1 次
index = vv.updateArray();
update(index);
}
}
//输出结果
public void show(){
vv.show();
}
//更新index下标顶点到周围顶点的距离和前驱节点
private void update(int index){
int len = 0;
//根据遍历我们邻接矩阵的 weight[index]行
for(int j = 0;j<weight[index].length;j++){
//这个距离是:初始顶点到index这个点的距离+index点的相邻节点的距离
//比如index为A点,就是遍历A点的相邻节点
//但是G到这个节点的距离就是GA的距离加上A到这个节点的距离
len = vv.getDis(index)+weight[index][j];
//如果j没有被访问过,并且len小于出发顶点到j点的距离,就要更新
if(!vv.visited(j) && len<vv.getDis(j)){
vv.updatePre(index,j);//更新j的前驱节点为index
vv.updateDis(j,len);//更新初始节点到j的距离为len
}
}
}
}
class VisitedVertex{
public int[] already_arr;//记录每个顶点是否访问过
public int[] per_visited;//每个顶点对应的前驱节点的下标数组
public int[] dis;//记录出发顶点到其他所有顶点的距离,如G为出发点,则会记录G到其他顶点的距离
//构造器
/**
*
* @param length 顶点的个数
* @param index 出发顶点对应的下标
*/
public VisitedVertex(int length,int index){
this.already_arr = new int[length];
this.per_visited = new int[length];
this.dis = new int[length];
//将初始节点设置为以访问
this.already_arr[index] = 1;
//初始化dis
Arrays.fill(dis,65535);
this.dis[index] = 0;//设置出发顶点到其他顶点的距离65535,到自己为0
}
//判断传入的节点是否访问过
public boolean visited(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 index
* @param pre
*/
public void updatePre(int index,int pre){
per_visited[pre] = index;
}
/**
* 返回出发顶点到index顶点的距离
* @param index
*/
public int getDis(int index){
return dis[index];
}
/**
* 继续选择并返回新的访问节点,例如G结束以后,就是处理A节点,因为A离G最近
* @return
*/
public int updateArray(){
int min = 65536;
int 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("===============================================================");
for(int i :already_arr){
System.out.print(i+" ");
}
System.out.println();
System.out.println("===============================================================");
for(int i:per_visited){
System.out.print(i+" ");
}
System.out.println();
System.out.println("===============================================================");
for(int i:dis){
System.out.print(i+" ");
}
}
}