编程实现路由算法.doc

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 = mintem?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:shortPath.keySet() System.out.print(从源点A到+vertex+的最短路径为); printPath(vertex); System.out.print(vertex); System.out.print(长度为：+shortPath.get(vertex); System.out.println( ); public static void printPath(String vertex) String node = shortPathWay.get(vertex); if(!node.equals(A)printPath(node); System.out.print(node+ ); class arcString startNode = ;String endNode = ;int weight =0;public arc(String startNode,String endNode,int weight) this.startNode = startNode; this.endNode = endNode; this.weight = weight; 实验结果（截图）：实验感想：Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一