Dijkstra算法求解最短路径问题（java代码实现）Dijkstra算法求解最短路径问题(java代码实现) java代码实现
package com.bingym.dijkstra;
import java.util.Arrays;
public class DijkstraAlgorithmNoDirectedGraph {
/*
* 利⽤Dijkstra算法求解最短路径问题
* 此时为⽆向图，顶点分别为:'A', 'B', 'C', 'D', 'E', 'F', 'G'七个顶点 * 求解每个顶点到其他所有顶点的最短路径
* 其中:N表⽰⽆法到达：下⾯包括到达⾃⾝(⽆法到达⾃⾝顶点)
* 'A'到其他顶点的距离为:{N,5,7,N,N,N,2}; * 'B'到其他顶点的距离为:{5,N,N,9,N,N,3};
* 'C'到其他顶点的距离为:{7,N,N,N,8,N,N};
* 'D'到其他顶点的距离为:{N,9,N,N,N,4,N};
* 'E'到其他顶点的距离为:{N,N,8,N,N,5,4};
* 'F'到其他顶点的距离为:{N,N,N,4,5,N,6};
* 'G'到其他顶点的距离为:{2,3,N,N,4,6,N};
* */
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);
//测试⽆向图是否创建成功
System.out.println("此时A,B,C,D,E,F,G七个顶点构成的⽆向图如下所⽰:");
graph.showGraph();
/
/测试Dijkstra算法
int startIndex =2;
graph.dijkstra(startIndex);
graph.showDijkstra(startIndex);
}
}
//定义⼀个⽆向图：将顶点以及顶点之间的距离(⽤邻接矩阵表⽰)
class Graph {
//定义⽆向图的需要的属性：顶点集合，邻接矩阵，以及已经访问的顶点的集合(VisitedVertexArr) private char[] vertex;//保存顶点的数组
private int[][] matrix;//邻接矩阵的⼆维数组
/
/已经访问的顶点的集合
private VisitedVertex vv;
//定义图的构造器
public Graph(char[] vertex,int[][] matrix){
this.vertex = vertex;
this.matrix = matrix;
}
//定义该⽆向图的api
//⽅法1：显⽰⽆向图的邻接矩阵
public void showGraph(){
for(int[] link : matrix){
System.out.String(link));
}
}
//⽅法2：更新index下标的顶点到周围顶点的距离以及周围顶点的前驱顶点
private void update(int index){
int len =0;
//根据遍历我们的邻接矩阵对应的index⾏的得到index到其他顶点的距离
for(int j =0; j < matrix[index].length; j++){
//此时我们需要计算出发顶点到index顶点的距离 + index顶点到其他顶点(j)的距离之和
len = vv.getDis(index)+ matrix[index][j];
if(!vv.isVisited(j)&& len < vv.getDis(j)){
/
/如果j顶点还未访问过，并且len⼩于出发顶点到j的距离，我们就进⾏出发顶点到j顶点的新⽅案的更新 vv.updatePre(j,index);
vv.updateDis(j,len);
}
}
}
//⽅法3:Dijkstra算法
public void dijkstra(int index){
//int count = 0;
vv =new VisitedVertex(vertex.length,index);//vertex.length为顶点的个数,index为开始的顶点//vv.path[0] = vertex[index];
update(index);//更新index顶点:⽬前为起始顶点到周围顶点的距离，以及更新前驱顶点
for(int j =1; j < vertex.length; j++){
//记录新的访问顶点，并更新index顶点到周围顶点的距离以及前驱顶点
index = vv.updateArr();//选择并返回新的访问顶点
//vv.path[++count] = vertex[index];
update(index);//然后更新新的index，直到所有顶点都访问完，即到起始顶点到其他顶点的最短路径}
}
public void showDijkstra(int index){//index表⽰开始的顶点
vv.show(index);;
}
}
//定义已访问的顶点的集合类
class VisitedVertex {
//定义属性:
//1.记录各个顶点是否已经访问过:1表⽰已经访问过,0表⽰仍未访问
public int[] isVisited;
//2.记录每⼀顶点在达到最短路径的前⼀个顶点：即每⼀个顶点的前驱顶点
public int[] preVisited;
//3.记录出发顶点到其他所有顶点的最短距离:
public int[] dis;
//4.记录实现最短路径的路径
//public char[] path;
//定义构造器
/
/vertexNum：表⽰顶点的个数;index表⽰出发顶点的下标
public VisitedVertex(int vertexNum,int index){
this.isVisited =new int[vertexNum];
this.preVisited =new int[vertexNum];
this.dis =new int[vertexNum];
//this.path = new char[vertexNum];
//初始化dis数组
Arrays.fill(dis,65535);//将dis初始化为65535：最⼤值
this.isVisited[index]=1;//将出发顶点设置为被访问过
this.dis[index]=0;//设置出发顶点到⾃⾝的访问距离为0
}
/
/定义api
//⽅法1：判断index下标的顶点是否访问过
//若访问过，返回true；若未访问，返回false
public boolean isVisited(int index){
return isVisited[index]==1;//即该数组对应下标数值是否为1
}
//⽅法2：更新出发顶点到index顶点的距离
public void updateDis(int index,int len){
dis[index]= len;
}
//⽅法3.更新此时距离index下标顶点最短路径的顶点pre为index顶点的的前驱顶点public void updatePre(int pre,int index){
preVisited[pre]= index;
}
//⽅法4：返回出发顶点到index顶点的距离
public int getDis(int index){
return dis[index];
}
//⽅法5：继续选择并返回新的访问顶点
public int updateArr(){
int min =65535;
int index =0;
for(int i =0; i < isVisited.length; i++){
if(isVisited[i]==0&& dis[i]< min){
min = dis[i];
index = i;
}
}
//更新index顶点为已经访问过
isVisited[index]=1;
return index;
}
//⽅法6：显⽰最后的最短路径结果
public void show(int index){
char[] vertex ={'A','B','C','D','E','F','G'};
int count =0;
System.out.println(vertex[index]+"顶点到下⾯顶点的最短路径为:");
for(int i : dis){
if(i !=65535){
System.out.print(vertex[count]+"("+ i +") ");
}else{
System.out.println("N");
}差速防坠器
count++;
count++;
}
System.out.println();
/*count = 1;
无水厕所while(count < path.length) {
System.out.println("顶点" + path[0] + "到顶点" + path[count] + "最短路径为: ");
for (int i = 0; i <= count; i++) {
System.out.print(path[i] + "->");
}
count++;
System.out.println();
}*/
}
}
输出结果:
夜光路面此时A,B,C,D,E,F,G七个顶点构成的⽆向图如下所⽰:
[65535,5,7,65535,65535,65535,2]
[5,65535,65535,9,65535,65535,3]
[7,65535,65535,65535,8,65535,65535]
[65535,9,65535,65535,65535,4,65535]
[65535,65535,8,65535,65535,5,4]
[65535,65535,65535,4,5,65535,6]
[2,3,65535,65535,4,6,65535]
C顶点到下⾯顶点的最短路径为:
A(7)B(12)C(0)D(17)E(8)F(13)G(9
java代码实现
package com.bingym.dijkstra;
import java.util.ArrayList;
import java.util.List;
public class DijkstraAlgorithmDirectedGraph {
/*
* Dijkstra算法求解有向图的最短路径问题
* 存在顶点1~6，构成有向图:
* 要求：求解顶点1到其他五个顶点的最短路径
*
* */
//主函数
public static void main(String[] args){
//构建顶点以及顶点间距离的数组，其中若相邻的顶点之间没有路径，则设置其距离为100 int len[][]=new int[7][];悬挂式指示牌
//第⼀⾏和第⼀列均为0：不使⽤，使得顶点的编号和数组的下标能够对上
len[0]=new int[]{0,0,0,0,0,0,0};
len[1]=new int[]{0,0,9,4,100,100,100};
len[2]=new int[]{0,100,0,100,12,5,100};
len[3]=new int[]{0,100,4,0,100,13,100};
len[4]=new int[]{0,100,100,100,0,100,2};
len[5]=new int[]{0,100,100,100,3,0,15};
len[6]=new int[]{0,100,100,100,100,100,0};
//确定顶点的个数
int num =6;
int dis[]=new int[num +1];
/
/dis数组⽤于存储1顶点到各个顶点的最短距离，先根据有向图存⼊初始值
for(int j =0;j < len.length;j++){
dis[j]= len[1][j];
}
//利⽤Dijkstra算法查1顶点到各个顶点的最短路径的函数⽅法
findMinPath(len,dis,num);
}
//Dijkstra算法实现查每两个顶点之间最短距离的函数
private static void findMinPath(int[][] len,int[] dis,int n){
//定义⼀个标记flag
int flag =1;//表⽰第⼀个顶点
int biaoJi[]=new int[n +1];//n+1=7 {空出第biaoJi[0]，只使⽤biaoJi[1]~biaoJi[6]使得顶点的数字和数组的下标对应上} //定义⼀个存储最短路径顶点的集合
List<Integer> list =new ArrayList<Integer>();
list.add(flag);//将顶点1加⼊最短路径集合
biaoJi[flag]=1;//先将顶点1标记，相当于将1顶点加⼊X集合，其余2-6顶点未标记1，加⼊Y集合//Dijkstra算法实现
for(int i =2;i <= n;i++){//从第⼆个顶点(即顶点2)开始遍历
//定义Integer.MAX_VALUE，作为路径距离的最⼩值参考值
int min = Integer.MAX_VALUE;
for(int j =1;j <= n;j++){
的制备
if(biaoJi[j]==0&& min >= dis[j]){
min = dis[j];
flag = j;
}
}
//将新增的最短路径的顶点加⼊到集合X中，即令其biaoJi[flag] = 1，达到X集合增加,Y集合减少的结果;
biaoJi[flag]=1;
//将最短路径的顶点添加到最短路径顶点集合中
list.add(flag);
for(int k =1;k <= n;k++){
dis[k]=minDis(dis[flag]+ len[flag][k],dis[k]);
}
//System.out.println("1顶点到" + flag + "顶点的最短路径距离是" + dis[flag]);
}
//输出打印顶点1到其他顶点的最短距离和最短路径
int count =1;
while(count <6){
System.out.println("1顶点到"+ (count)+"顶点的最短路径为:"+ (count)]);
for(int i =0;i <= count;i++){
if(i != count){
System.out.(i)+">>");
}else{
System.out.(i));
}
加固显示器
}
System.out.println("");
count++;
}
}
//求最⼩值并返回其最⼩值的函数
private static int minDis(int i,int j){
return(i<=j)? i : j;
}
}
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议