java实现单源最短路径
本文采用java实现单源最短路径，并带有略微详细的注解，供大家参考，具体内容如下
packagecom.qf.greaph;
importjava.util.ArrayList;
importjava.util.Arrays;
importjava.util.HashMap;
importjava.util.Map;
importjava.util.Map.Entry;
/**
*@authorjiayoo
*7/30
*Dijkstra最短路径算法是一种单源最短路径
*本文采用的是邻接表表示图。
*
*图的表示：1.采用ArrayList来储存图的顶点
*2.采用Map来储存边集，map可以实现一对多的关系，因此能很好的实现邻接表结构
*3.采用ArrayList的原因是使边集有序这样，Node的里面那个记录距离的集合才能一一对应
*/
publicclassMinPath{
privatestaticclassgraph{
privateArrayListnodes=newArrayList<>();//表示图顶点，同时他也作为V集合
privateMap>adjaNode=newHashMap<>();//表示图的边
privateArrayListnodes1;//表示S集合,即存储已经访问的节点，
privatefloat[]minPath;//用来存储源点到每个顶点的距离
floatmin=Float.MAX_VALUE;
/**
*@paramstart
*@paramend
*@paramdistance
*构建邻接表。使之成为图
*/
publicvoidaddAdjaNode(Node1start,Node1end,floatdistance){
if(!nodes.contains(start)){
nodes.add(start);
}
if(!nodes.contains(end)){
nodes.add(end);
}
if(adjaNode.containsKey(start)&&adjaNode.get(start).contains(end)){
return;
}
if(adjaNode.containsKey(start)){
adjaNode.get(start).add(end);
}else{
ArrayListnode=newArrayList();
node.add(end);
adjaNode.put(start,node);
}
start.distonext.add(distance);
}
/**
*将图打印出来
*/
publicvoidprinGraph(){
if(nodes==null||adjaNode==null){
System.out.println("图为空");
return;
}
for(Entry>entry:adjaNode.entrySet()){
System.out.println("顶点："+entry.getKey().name+"链接顶点有：");
for(inti=0;i();//存储已经遍历过的点
minPath=newfloat[nodes.size()];//初始化距离数组
inti;
/*
*对最短路径进行初始化，设置源点到其他地方的值为无穷大
**/
for(i=0;in=adjaNode.get(node);//获取到源点的边集
/*
*先对源节点进行初始化
*1.对距离数组进行初始化。
*2.找到源点到某个距离最短的点，并标记
*
**/
for(i=0;inode.distonext.get(i)){
min=node.distonext.get(i);
node1=n.get(i);//找到当前最短路径
}
}
this.process(node1,min);
}
privatevoidprocess(Node1node,floatdistance){
min=Float.MAX_VALUE;//作为标记
Node1node1=null;//同样记录距离最短的点
inti;
ArrayListn=adjaNode.get(node);//获得边集
for(i=0;iminPath[i]){
min=minPath[i];
node1=nodes.get(i);
}
}
}
if(node1!=null){
node1.visited=true;
process(node1,min);//源点到当前的距离
}else{//说明此位置没有后续节点，或者已经全部被访问完了，则到达此位置只需要加上此位置的值
}
}
}
publicstaticvoidmain(String[]args){
Node1n1=newNode1(0,"A");
Node1n2=newNode1(1,"B");
Node1n3=newNode1(2,"C");
Node1n4=newNode1(3,"D");
Node1n5=newNode1(4,"E");
Node1n6=newNode1(5,"F");
graphgp=newgraph();
gp.addAdjaNode(n1,n2,6);
gp.addAdjaNode(n2,n1,6);
gp.addAdjaNode(n1,n3,3);
gp.addAdjaNode(n3,n1,3);
gp.addAdjaNode(n2,n3,2);
gp.addAdjaNode(n3,n2,2);
gp.addAdjaNode(n2,n4,5);
gp.addAdjaNode(n4,n2,5);
gp.addAdjaNode(n3,n4,3);
gp.addAdjaNode(n4,n3,3);
gp.addAdjaNode(n3,n5,4);
gp.addAdjaNode(n5,n3,4);
gp.addAdjaNode(n4,n5,2);
gp.addAdjaNode(n5,n4,2);
gp.addAdjaNode(n4,n6,3);
gp.addAdjaNode(n6,n4,3);
gp.addAdjaNode(n5,n6,5);
gp.addAdjaNode(n6,n5,5);
//下面尝试一下非连通图
///**
//*权值：1
//*A-----------B
//*权|*
//*值|*权值：3
//*2|*
//*C-----D
//*权值：5
//*
//*
//**/
//
//gp.addAdjaNode(n1,n2,1);
//gp.addAdjaNode(n2,n1,1);
//
//gp.addAdjaNode(n1,n3,2);
//gp.addAdjaNode(n3,n1,2);
//
//gp.addAdjaNode(n1,n4,3);
//gp.addAdjaNode(n4,n1,3);
//
//gp.addAdjaNode(n3,n4,5);
//gp.addAdjaNode(n4,n3,5);
gp.prinGraph();
System.out.println("--------------------------------------------------------------------");
System.out.println("此数组下标代表id，值代表从源点分别到各点的最短距离，A开始的下标是0，B、C、D等依次类推，并且源点默认设置为id为零0的开始");
gp.findMinPath();
System.out.println(Arrays.toString(gp.minPath));
}
}
/**
*顶点类
*/
classNode1{
Stringname;
booleanvisited=false;//访问状态。有效减少原算法移除V集合中元素所花费的时间
intid=-1;//设置默认id为-1
ArrayListdistonext=newArrayList<>();//这一点到另外每一个点的距离
publicNode1(intid,Stringname){
this.id=id;
this.name=name;
}
}
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。