单源最短路径-分支界限法-优先队列式。这里使用无回路的有向图，便于构建树。构建好树后，从根结点作为起始源，加入结点队列，然后判断获取队列中最短的路径结点做为活结点，将活结点的所有子结点加入队列，移除活结点。这里需要注意活结点的子结点加入时需要判断是否在现有队列中已存在同一个路径点(就是有向图的点)，如果存在需要用最短的替换，就是分支界限法中所谓的剪枝。packagetest;
importjava.util.ArrayList;
importjava.util.HashMap;
importjava.util.List;
importjava.util.Map;
/**
*Createdbysaishangmingzhuon/12/4.
*单源最短路径
*/
publicclassSingleSourceShortestPath{
publicstaticvoidmain(String[]arg){
newSingleSourceShortestPath().branchAndBoundMethod();
}
/**
*分支界限法-优先队列式
*/
publicvoidbranchAndBoundMethod(){
ListpointList=newArrayList<>();
pointList.add(newPoint("A",0));
pointList.add(newPoint("B",0));
pointList.add(newPoint("C",0));
pointList.add(newPoint("D",0));
pointList.add(newPoint("E",0));
pointList.add(newPoint("F",0));
pointList.add(newPoint("G",0));
pointList.add(newPoint("H",0));
pointList.add(newPoint("I",0));
pointList.add(newPoint("J",0));
pointList.add(newPoint("K",0));
MappathMap=newHashMap<>();
pathMap.put("AB",2);
pathMap.put("AC",3);
pathMap.put("AD",4);
pathMap.put("BE",7);
pathMap.put("BF",2);
pathMap.put("BC",3);
pathMap.put("CF",9);
pathMap.put("CG",2);
pathMap.put("DG",2);
pathMap.put("EH",1);
pathMap.put("EI",1);
pathMap.put("FI",3);
pathMap.put("FG",2);
pathMap.put("GI",5);
pathMap.put("GJ",1);
pathMap.put("HK",1);
pathMap.put("IK",1);
pathMap.put("JI",2);
pathMap.put("JK",2);
//构造树
Noderoot=newNode(pointList.get(0),"A",0);
again(pointList,pathMap,root);
System.out.println(root);
ListnodeList=newArrayList<>();
ListresultNodeList=newArrayList<>();
nodeList.add(root);
while(nodeList.size()>0){
//判断list中最小的结点node
NodeliveNode=getMinNode(nodeList);
//做为活结点，记录，取出子结点list
resultNodeList.add(liveNode);
ListchildList=liveNode.getChildNodeList();
for(NodechildNode:childList){
//判断子结点中是否有重复的路径点point
//if重复，取短的
//else，加入nodelist
addNode(childNode,nodeList);
}
//移除活结点
nodeList.remove(liveNode);
}
for(Nodenode:resultNodeList){
System.out.println(node.getPoint().getName()+":"+node.getPath()+":"+node.getValue());
}
}
publicvoidaddNode(NodechildNode,ListnodeList){
booleanflag=true;
for(Nodenode:nodeList){
if(node.getPoint()==childNode.getPoint()){
if(node.getValue()>childNode.getValue()){
node=childNode;
}
flag=false;
}
}
if(flag){
nodeList.add(childNode);
}
}
publicNodegetMinNode(ListnodeList){
intminV=Integer.MAX_VALUE;
NodeminNode=null;
for(Nodenode:nodeList){
if(node.getValue()
minV=node.getValue();
minNode=node;
}
}
returnminNode;
}
privatevoidagain(ListpointList,MappathMap,Nodeparent){
for(Pointp:pointList){
Stringkey=parent.getPoint().getName()+p.getName();
if(pathMap.containsKey(key)){
Nodenode=newNode(p,parent.getPath()+p.getName(),parent.getValue()+pathMap.get(key));
parent.getChildNodeList().add(node);
again(pointList,pathMap,node);
}
}
}
classNode{
Pointpoint;
Stringpath;
intvalue;
ListchildNodeList=newArrayList<>();
publicNode(Pointpoint,Stringpath,intvalue){
this.point=point;
this.path=path;
this.value=value;
}
publicListgetChildNodeList(){
returnchildNodeList;
}
publicvoidsetChildNodeList(ListchildNodeList){
this.childNodeList=childNodeList;
}
publicPointgetPoint(){
returnpoint;
}
publicvoidsetPoint(Pointpoint){
this.point=point;
}
publicStringgetPath(){
returnpath;
}
publicvoidsetPath(Stringpath){
this.path=path;
}
publicintgetValue(){
returnvalue;
}
publicvoidsetValue(intvalue){
this.value=value;
}
}
}
classPoint{
Stringname;
intindex;
publicPoint(Stringname,intindex){
this.name=name;
this.index=index;
}
publicStringgetName(){
returnname;
}
publicvoidsetName(Stringname){
this.name=name;
}
publicintgetIndex(){
returnindex;
}
publicvoidsetIndex(intindex){
this.index=index;
}
}
