编程实现路由算法(共5页).doc

《编程实现路由算法(共5页).doc》由会员分享，可在线阅读，更多相关《编程实现路由算法(共5页).doc（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上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

2、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

3、,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 th

4、e 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(); whi

5、le(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

6、 getOldPath(lastVisitedNode)+newPath) resetShortPath(unvisitNode,getOldPath(lastVisitedNode)+newPath); shortPathWay.put(unvisitNode,lastVisitedNode);/后继前驱 /如果原来不可达的话，但是通过中间节点可以到达，那么同样要改变shortPath else resetShortPath(unvisitNode,getOldPath(lastVisitedNode)+newPath); shortPathWay.put(unvisitNode,lastV

7、isitedNode); 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

8、) 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 delN

9、ode,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 r

10、esetShortPath(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, S

11、tring 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(从源

12、点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 startN

13、ode = ;String endNode = ;int weight =0;public arc(String startNode,String endNode,int weight) this.startNode = startNode; this.endNode = endNode; this.weight = weight; 实验结果（截图）：实验感想：Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等，我主要是通过数据结构和离散数学的图论得到的结果。Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表的方式，这里均采用永久和临时标号的方式。专心-专注-专业