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<>();//表示图的边 privateArrayList nodes1;//表示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{ ArrayList node=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;i n=adjaNode.get(node);//获取到源点的边集 /* *先对源节点进行初始化 *1.对距离数组进行初始化。 *2.找到源点到某个距离最短的点,并标记 * **/ for(i=0;i node.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; ArrayList n=adjaNode.get(node);//获得边集 for(i=0;i minPath[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 ArrayList distonext=newArrayList<>();//这一点到另外每一个点的距离 publicNode1(intid,Stringname){ this.id=id; this.name=name; } }
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持毛票票。