问题描述
java实现Dijkstra算法（其它算法也可），求全局最短路径（图中任意两点的最短路径），求帮助！如下图，图中的权值都设为1。贴出完整代码，将不胜感激！
解决方案
本帖最后由 wawfully 于 2014-10-10 18:38:16 编辑
解决方案二：
还是别偷懒了吧，照着书上敲就行了，自己学习一下吧
解决方案三：
看不懂Dijkstra算法
解决方案四：
下面代码改编自http://blog.csdn.net/a9529lty/article/details/4047319去掉B1至C1的边，运行结果：[A1,A2]:1.0[A1,A2,A3]:2.0[A1,A2,B3]:2.0[A1,A2,A3,A4]:3.0[A1,A2,B3,B2]:3.0[A1,A2,A3,B4]:3.0[A1,A2,B3,C4]:3.0[A1,A2,A3,A4,A5]:4.0[A1,A2,B3,B2,B1]:4.0[A1,A2,A3,B4,B5]:4.0[C1,A1]:-1.0[C2,A1]:-1.0[A1,A2,B3,C4,C3]:4.0[A1,A2,B3,C4,C5]:4.0保留B1至C1的边，运行结果：[A1,A2]:1.0[A1,A2,A3]:2.0[A1,A2,B3]:2.0[A1,A2,A3,A4]:3.0[A1,A2,B3,B2]:3.0[A1,A2,A3,B4]:3.0[A1,A2,B3,C4]:3.0[A1,A2,A3,A4,A5]:4.0[A1,A2,B3,B2,B1]:4.0[A1,A2,A3,B4,B5]:4.0[A1,A2,B3,C4,C3]:4.0[A1,A2,B3,C4,C5]:4.0[A1,A2,B3,B2,B1,C1]:5.0[A1,A2,B3,C4,C3,C2]:5.0为什么去掉B1至C1的边，[C1,A1]和[C2,A1]就不连通了，[B3,C4]的边也可以使[C1,A1]、[C2,A1]连通啊？B1至C1边的连通的代码是下面两行：//map.add(newSide("B1","C1",1));//map.add(newSide("C1","B1",1));
完整代码：importjava.util.ArrayList;publicclassDijkstra2{staticArrayList<Side>map=null;staticArrayList<String>redAgg=null;staticArrayList<String>blueAgg=null;staticSide[]parents=null;publicstaticvoidmain(String[]args){//初始化顶点集String[]nodes={"A1","A2","A3","A4","A5","B1","B2","B3","B4","B5","C1","C2","C3","C4","C5"};//初始化有向权重图map=newArrayList<Side>();map.add(newSide("A1","A2",1));map.add(newSide("A2","A1",1));map.add(newSide("A2","A3",1));map.add(newSide("A3","A2",1));map.add(newSide("A3","A4",1));map.add(newSide("A4","A3",1));map.add(newSide("A4","A5",1));map.add(newSide("A5","A4",1));map.add(newSide("B1","B2",1));map.add(newSide("B2","B1",1));map.add(newSide("B2","B3",1));map.add(newSide("B3","B2",1));map.add(newSide("B3","B4",1));map.add(newSide("B4","B3",1));map.add(newSide("B4","B5",1));map.add(newSide("B5","B4",1));map.add(newSide("C1","C2",1));map.add(newSide("C2","C1",1));map.add(newSide("C2","C3",1));map.add(newSide("C3","C2",1));map.add(newSide("C3","C4",1));map.add(newSide("C4","C3",1));map.add(newSide("C4","C5",1));map.add(newSide("C5","C4",1));map.add(newSide("A2","B3",1));map.add(newSide("B3","A2",1));map.add(newSide("A3","B4",1));map.add(newSide("B4","A3",1));map.add(newSide("B3","C4",1));map.add(newSide("C4","B3",1));//map.add(newSide("B1","C1",1));//map.add(newSide("C1","B1",1));//初始化已知最短路径的顶点集，即红点集，只加入顶点0redAgg=newArrayList<String>();redAgg.add(nodes[0]);//初始化未知最短路径的顶点集,即蓝点集blueAgg=newArrayList<String>();for(inti=1;i<nodes.length;i++)blueAgg.add(nodes[i]);//初始化每个顶点在最短路径中的父结点,及它们之间的权重,权重-1表示无连通parents=newSide[nodes.length];parents[0]=newSide("-1",nodes[0],0);for(inti=0;i<blueAgg.size();i++){Stringn=blueAgg.get(i);parents[i+1]=newSide(nodes[0],n,getWeight(nodes[0],n));}//找从蓝点集中找出权重最小的那个顶点,并把它加入到红点集中while(blueAgg.size()>0){MinShortPathmsp=getMinSideNode();if(msp.getWeight()==-1)msp.outputPath(nodes[0]);elsemsp.outputPath();Stringnode=msp.getLastNode();redAgg.add(node);//如果因为加入了新的顶点,而导致蓝点集中的顶点的最短路径减小,则要重要设置setWeight(node);}}/***//***得到一个节点的父节点**@paramparents*@paramnode*@return*/publicstaticStringgetParent(Side[]parents,Stringnode){if(parents!=null){for(Sidend:parents){if(nd.getNode()==node){returnnd.getPreNode();}}}return"-1";}/***//***重新设置蓝点集中剩余节点的最短路径长度**@parampreNode*@parammap*@paramblueAgg*/publicstaticvoidsetWeight(StringpreNode){if(map!=null&&parents!=null&&blueAgg!=null){for(Stringnode:blueAgg){MinShortPathmsp=getMinPath(node);floatw1=msp.getWeight();if(w1==-1)continue;for(Siden:parents){if(n.getNode()==node){if(n.getWeight()==-1||n.getWeight()>w1){n.setWeight(w1);n.setPreNode(preNode);//重新设置顶点的父顶点break;}}}}}}/***//***得到两点节点之间的权重**@parammap*@parampreNode*@paramnode*@return*/publicstaticfloatgetWeight(StringpreNode,Stringnode){if(map!=null){for(Sides:map){if(s.getPreNode().equals(preNode)&&s.getNode().equals(node))returns.getWeight();}}return-1;}/***//***从蓝点集合中找出路径最小的那个节点**@parammap*@paramblueAgg*@return*/publicstaticMinShortPathgetMinSideNode(){MinShortPathminMsp=null;if(blueAgg.size()>0){intindex=0;for(intj=0;j<blueAgg.size();j++){MinShortPathmsp=getMinPath(blueAgg.get(j));if(minMsp==null||msp.getWeight()!=-1&&msp.getWeight()<minMsp.getWeight()){minMsp=msp;index=j;}}blueAgg.remove(index);}returnminMsp;}/***//***得到某一节点的最短路径(实际上可能有多条,现在只考虑一条)**@paramnode*@return*/publicstaticMinShortPathgetMinPath(Stringnode){MinShortPathmsp=newMinShortPath(node);if(parents!=null&&redAgg!=null){for(inti=0;i<redAgg.size();i++){MinShortPathtempMsp=newMinShortPath(node);Stringparent=redAgg.get(i);StringcurNode=node;while(!"-1".equals(parent)){floatweight=getWeight(parent,curNode);if(weight>-1){tempMsp.addNode(parent);tempMsp.addWeight(weight);curNode=parent;parent=getParent(parents,parent);}elsebreak;}if(msp.getWeight()==-1||tempMsp.getWeight()!=-1&&msp.getWeight()>tempMsp.getWeight())msp=tempMsp;}}returnmsp;}}/***//***图中的有向边，包括节点名及他的一个前向节点名，和它们之间的权重**/classSide{privateStringpreNode;//前向节点privateStringnode;//后向节点privatefloatweight;//权重publicSide(StringpreNode,Stringnode,floatweight){this.preNode=preNode;this.node=node;this.weight=weight;}publicStringgetPreNode(){returnpreNode;}publicvoidsetPreNode(StringpreNode){this.preNode=preNode;}publicStringgetNode(){returnnode;}publicvoidsetNode(Stringnode){this.node=node;}publicfloatgetWeight(){returnweight;}publicvoidsetWeight(floatweight){this.weight=weight;}}classMinShortPath{privateArrayList<String>nodeList;//最短路径集privatefloatweight;//最短路径publicMinShortPath(Stringnode){nodeList=newArrayList<String>();nodeList.add(node);weight=-1;}publicArrayList<String>getNodeList(){returnnodeList;}publicvoidsetNodeList(ArrayList<String>nodeList){this.nodeList=nodeList;}publicvoidaddNode(Stringnode){if(nodeList==null)nodeList=newArrayList<String>();nodeList.add(0,node);}publicStringgetLastNode(){intsize=nodeList.size();returnnodeList.get(size-1);}publicfloatgetWeight(){returnweight;}publicvoidsetWeight(floatweight){this.weight=weight;}publicvoidoutputPath(){outputPath("-1");}publicvoidoutputPath(StringsrcNode){Stringresult="[";if(!"-1".equals(srcNode))nodeList.add(srcNode);for(inti=0;i<nodeList.size();i++){result+=""+nodeList.get(i);if(i<nodeList.size()-1)result+=",";}result+="]:"+weight;System.out.println(result);}publicvoidaddWeight(floatw){if(weight==-1)weight=w;elseweight+=w;}}