精选优质文档-----倾情为你奉上import java.util.ArrayList;import java.util.LinkedHashMap;public class shutPath {static int[][] cost;static ArrayList visited = new ArrayList();static ArrayList unVisited = new ArrayList();static ArrayList vertexs = new ArrayList();static LinkedHashMap shortPath = new LinkedHashMap();static ArrayList arcs = new ArrayList();static LinkedHashMap shortPathWay = new LinkedHashMap();public static void main(String[] args) { // TODO Auto-generated method stub //init the verges set arcs.add(new arc("A","B",2)); arcs.add(new arc("A","C",4)); arcs.add(new arc("A","D",15)); arcs.add(new arc("B","D",5)); arcs.add(new arc("B","C",1)); arcs.add(new arc("C","D",7)); arcs.add(new arc("D","E",4)); //init the nodes set vertexs.add("A"); vertexs.add("B"); vertexs.add("C"); vertexs.add("D"); vertexs.add("E"); // init the novisited set visited.add("A"); //init the visited set unVisited.add("B"); unVisited.add("C"); unVisited.add("D"); unVisited.add("E"); //init the shortPath map for(String unvisitNode:unVisited) { boolean access = false; for(arc a:arcs) { if(a.startNode.equals("A") && a.endNode.equals(unvisitNode)) { shortPath.put(unvisitNode,a.weight); access = true; break; } } if(access == false) { shortPath.put(unvisitNode, -1); } }//把第一个临近节点的前驱找到 initFirstShortPathWay(); while(unVisited.size()>0){ String lastVisitedNode = getLastVisitedNode(); for(String unvisitNode:unVisited) { //获得最后一访问节点到未访问节点到距离 int newPath = getWeight(lastVisitedNode,unvisitNode); if(newPath > 0) { //获得源点到未访问节点的距离 int oldPath = getOldPath(unvisitNode); //如果二者都存在话，改变shortPath 的相应值为最小值 if(oldPath > 0) { if(oldPath > getOldPath(lastVisitedNode)+newPath){ resetShortPath(unvisitNode,getOldPath(lastVisitedNode)+newPath); shortPathWay.put(unvisitNode,lastVisitedNode);//后继——前驱 } } //如果原来不可达的话，但是通过中间节点可以到达，那么同样要改变shortPath else { resetShortPath(unvisitNode,getOldPath(lastVisitedNode)+newPath); shortPathWay.put(unvisitNode,lastVisitedNode); } } } String minNode = getTheMinPathNode(); removeNode(minNode,unVisited); addNode(minNode,visited); } //输出最终结果 printResult();} //初始化第一个 路径的前驱public static void initFirstShortPathWay(){ int min = 500; String firstNode =""; for(String vertex:shortPath.keySet()) { int tem = shortPath.get(vertex); if(tem > 0){ min = min > tem?tem:min; } } for(String vertex:shortPath.keySet()) { if(min == shortPath.get(vertex))firstNode = vertex; } shortPathWay.put(firstNode,"A"); }//add a node to the setpublic static void addNode(String node,ArrayList set){ set.add(node);}// remove a node of the setpublic static void removeNode(String delNode,ArrayList set){ int index = 0; for(int i=0;i0){ min = min>tem?tem:min; } } for(String unode:unVisited) { if(min == shortPath.get(unode))node=unode; } return node;}//得到源点到未访问结点的最短距离public static int getOldPath(String node){ if(node.equals("A"))return 0; return shortPath.get(node);}//重新设定 shortPathpublic static void resetShortPath(String node,int path){ for(String snode:shortPath.keySet()) { if(snode.equals(node))shortPath.put(snode, path); }} //get the last node of the visited setpublic static String getLastVisitedNode(){ return visited.get(visited.size()-1);}// get the weightpublic static int getWeight(String startNode, String endNode){ int weight=-1; for(arc a:arcs) { if(a.startNode.equals(startNode) && a.endNode.equals(endNode)) { weight = a.weight; System.out.println(a.startNode+"-->"+a.endNode+"="+weight); } } return weight;}// get the min numpublic static void printResult(){ for(String vertex:sho。
