通信网课设.doc

课程设计说明书 NO.1基于Java的Dijkstra最短路径算法1.课程设计的目的本课程设计是学习数据通信与通信网技术课程必要的教学环节。由于该课程是专业必修课，需要通过实践巩固基础知识，为使学生取得最现代化的设计技能和研究方法，课程设计训练也就成为了一个重要的教学环节。通过对路由算法的设计和实现，达到进一步完善对通信网基础及应用课程学习的效果。2.设计方案论证最短路径算法的介绍最常用的路径算法有：Dijkstra算法、A*算法、SPFA算法、Bellman-Ford算法、Floyd-Warshall算法、Johnson算法、所谓单源最短路径问题是指已知图G（V，E），我们希望找出从某给定的源结点SV到V中的每个结点的最短路径。首先，我们可以发现有这样一个事实：如果P是G中从vs到vj的最短路，vi是P中的一个点，那么，从vs沿P到vi的路是从vs到vi的最短路。最近在研究社会网络分析方面的一些特征值的计算，包括点度中心度、中间中心度以及接近中心度。而在所有的特征值计算中，中间中心度算是最难计算的一个。节点的中间中心度是指一个社会网络中，节点控制其他节点的能力，最早是由Freeman于1977年提出的用于衡量个体社会地位的参数。而在网络中进行量化时，u的节点中间中心度是指网络中任意两个节点的最短路径中经过u的数量比例之和。因此，要想知道某个节点的中间中心度，首先要寻找任意两个节点之间的最短路径。最短路径问题是图论研究中的一个经典算法问题，旨在寻找图中两结点之间的最短路径。算法具体的形式包括：确定起点的最短路径问题即已知起始结点，求最短路径的问题。确定终点的最短路径问题与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。确定起点终点的最短路径问题即已知起点和终点求两结点之间的最短路径。全局最短路径问题求图中所有的最短路径。用于解决最短路径问题的算法被称做“最短路径算法”， 有时被简称作“路径算法”。 沈 阳 大 学课程设计说明书 NO22.1 Dijkstra算法 首先,每次新扩展一个距离最短的点，更新与其相邻的点的距离。当所有边权都为正时，由于不会存在一个距离更短的没扩展过的点，所以这个点的距离永远不会再被改变，因而保证了算法的正确性。不过根据这个原理，用Dijkstra求最短路的图不能有负权边，因为扩展到负权边的时候会产生更短的距离，有可能就破坏了已经更新的点距离不会改变的性质。然后，引进一个辅助向量D，它的每个分量D表示当前所找到的从始点v到每个终点vi的最短路径的长度。如D3=2表示从始点v到终点3的路径相对最小长度为2。这里强调相对就是说在算法过程中D的值是在不断逼近最终结果但在过程中不一定就等于最短路径长度。它的初始状态为：若从v到vi有弧，则D为弧上的权值；否则置D为。显然，长度为 Dj=MinD | viV 的路径就是从v出发的长度最短的一条最短路径。此路径为(v,vj)。 那么，下一条长度次短的最短路径是哪一条呢？假设该次短路径的终点是vk，则可想而知，这条路径或者是(v,vk)，或者是(v,vj,vk)。它的长度或者是从v到vk的弧上的权值，或者是Dj和从vj到vk的弧上的权值之和。 一般情况下，假设S为已求得最短路径的终点的集合，则可证明：下一条最短路径（设其终点为X）或者是弧(v,x)，或者是中间只经过S中的顶点而最后到达顶点X的路径。因此，下一条长度次短的最短路径的长度必是Dj=MinD | viV-S 其中，D或者是弧(v/,vi)上的权值，或者是Dk(vkS)和弧(vk,vi)上的权值之和。 迪杰斯特拉算法描述如下：（1）arcs表示弧上的权值。若不存在，则置arcs为（在本程序中为MAXCOST）。S为已找到从v出发的最短路径的终点的集合，初始状态为空集。那么，从v出发到图上其余各顶点vi可能达到的最短路径长度的初值为D=arcsLocate Vex(G,v),i viV 2）选择vj，使得Dj=MinD | viV-S 修改从v出发到集合V-S上任一顶点vk可达的最短路径长度。2.1.1 Dijkstra算法的步骤Dijkstra算法是一种最短路径算法，用于计算一个节点到其它所有节点的最短路径，动态路由协议OSPF中就用到了Dijkstra算法来为路由计算最短路径。 沈 阳 大 学课程设计说明书 NO.3算法本身并不是按照我们的正常思维习惯，我们一般会，从原点遍历所有与之相连的节点，找到最短路径，再从最短路径上的那个点遍历与之相连的所有其它点（原点除外），然后依次类推。这样做虽然可以算出一个树形，但是在大多数情况下，这种算法会产生很多次优路径，也就是说非最短路径。Dijkstra算法的大概过程：假设有两个集合或者说两个表，表A和表B表A表示生成路径，表B表示最后确定的路径（1）.从原点出发，遍历检查所有与之相连的节点，将原点和这些节点存放到表A中，并记录下两节点之间的代价。（2）.将代价最小的代价值和这两节点移动到表B中（其中一个是原点）。（3）.把这个节点所连接的子节点找出，放入到表A中，算出子节点到原点的代价（4）.重复第二步和第三步直到表A为空。然后根据表B中的数据算出最优树。还有另一种说法，Dijkstra算法的输入包含了一个有权重的有向图G，以及G中的一个来源顶点S。 我们以V表示G中所有顶点的集合。 每一个图中的边，都是两个顶点所形成的有序元素对。(u,v)表示从顶点u到v有路径相连。 我们以E所有边的集合，而边的权重则由权重函数w: E 0, 定义。 因此，w(u,v)就是从顶点u到顶点v的非负花费值(cost)。 边的花费可以想像成两个顶点之间的距离。任两点间路径的花费值，就是该路径上所有边的花费值总和。 已知有V中有顶点s及t，Dijkstra算法可以找到s到t的最低花费路径(i.e. 最短路径)。 这个算法也可以在一个图中，找到从一个顶点s到任何其他顶点的最短路径。Dijstra算法的基础操作是边的拓展：如果存在一条从u到v的边，那么从s到u的最短路径可以通过将边(u,v)添加到尾部来拓展一条从s到v的路径。这条路径的长度是du+w(u,v)。如果这个值比目前已知的dv的值要小，我们可以用新值来替代当前dv中的值。拓展边的操作一直执行到所有的dv都代表从s到v最短路径的花费。这个算法经过组织因而当du达到它最终的值的时候没条边(u,v)都只被拓展一次。按路径长度递增次序产生最短路径算法：把V分成两组。S：已求出最短路径的顶点的集合V-S=T：尚未确定最短路径的顶点集合将T中顶点按最短路径递增的次序加入到S中，先从源点V0到S中各顶点的最短路径长度都不大于从V0到T中任何顶点的最短路径长度 沈 阳 大 学课程设计说明书 NO.4然后每个顶点对应一个距离值S中顶点：从V0到此顶点的最短路径长度T中顶点：从V0到此顶点的只包括S中顶点作中间顶点的最短路径长度依据：可以证明V0到T中顶点Vk的最短路径，或是从V0到Vk的直接路径的权值；或是从V0经S中顶点到Vk的路径权值之和初使时令 S=V0,T=其余顶点，T中顶点对应的距离值 若存在，为弧上的权值 若不存在，为从T中选取一个其距离值为最小的顶点W，加入S对T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值比不加W的路径要短，则修改此距离值重复上述步骤，直到S中包含所有顶点，即S=V为止 。Dijkstra算法基本思想为：设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径,就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。2.2 Floyd算法 Floyd 算法是解决单源最短路径问题的一个算法，其基本思想是，将顶点编号为1,2,3n。令最短长度为aij,在这条路中只允许前m个顶点作为中间顶点，如果aik+akjaij;则aij=aik+akj;负责，aij=，直至求出最短距离。2.2.1问题分析n个点组成一个带权有向图，选择其中一点作为始点，找出从始点到其余各点的最短路径。给出相应的数据结构，需要三个二维数组，*a：最优值矩阵；*r：路由矩阵；*c：两点之间的距离矩阵。初始时，对所有的节点，置previ=v。在Floyd算法中更新最短路径长度时，只要distu+cuidu+w(u,v) 沈 阳 大 学课程设计说明书 NO.8dv=du+w(u,v);prev=u;3.设计的过程与分析3.1设计内容通过设计一个Java程序，运用D算法，用以求图中各个节点之间得最短路径，最后利用程序求得节点1到各个节点之间得最短路径。 图3 最短路径3.2设计程序import java.util.ArrayList;public class Dijkstra static ArrayList map = null; static ArrayList redAgg = null; static ArrayList blueAgg = null; static Side parents = null; public static void main(String args) / 初始化顶点集 int nodes = 1, 2, 3, 4 ,5 ,6; / 初始化有向权重图- map = new ArrayList(); System.out.println(Dijkstra算法); map.add(new Side(1, 3, 1); map.add(new Side(1, 4, 1); map.add(new Side(1, 2, 2); map.add(new Side(1, 6, 3); map.add(new Side(2, 1, 2); map.add(new Side(2, 3, 2); map.add(new Side(2, 5, 3); 沈 阳 大 学课程设计说明书 NO.9map.add(new Side(3, 2, 2); map.add(new Side(3, 1, 2); map.add(new Side(4, 6, 4); map.add(new Side(4, 1, 1); map.add(new Side(5, 2, 3);map.add(new Side(5, 6, 1); map.add(new Side(6, 1, 3);map.add(new Side(6, 4, 4);map.add(new Side(6, 5, 1); / 初始化已知最短路径的顶点集，即红点集，只加入顶点0 redAgg = new ArrayList(); redAgg.add(nodes0); / 初始化未知最短路径的顶点集,即蓝点集 blueAgg = new ArrayList(); for (int i = 1; i nodes.length; i+) blueAgg.add(nodesi); / 初始化每个顶点在最短路径中的父结点,及它们之间的权重,权重-1表示无连通 parents = new Sidenodes.length; parents0 = new Side(-1, nodes0, 0); for (int i = 0; i 0) MinShortPath msp = getMinSideNode(); if(msp.getWeight()=-1) msp.outputPath(nodes0); else msp.outputPath(); int node = msp.getLastNode(); redAgg.add(node); / 如果因为加入了新的顶点,而导致蓝点集中的顶点的最短路径减小,则要重要设置 setWeight(node); 沈 阳 大 学课程设计说明书 NO.10/* */* * 得到一个节点的父节点 * * param parents * param node * return */ public static int getParent(Side parents, int node) if (parents != null) for (Side nd : parents) if (nd.getNode() = node) return nd.getPreNode(); return -1; /* */* * 重新设置蓝点集中剩余节点的最短路径长度* * param preNode * param map * param blueAgg */ public static void setWeight(int preNode) if (map != null & parents != null & blueAgg != null) for (int node : blueAgg) MinShortPath msp=getMinPath(node); int w1 = msp.getWeight(); if (w1 = -1) continue; for (Side n : parents) if (n.getNode() = node) if (n.getWeight() = -1 | n.getWeight() w1) n.setWeight(w1); n.setPreNode(preNode);/重新设置顶点的父顶点 break; 沈 阳 大 学课程设计说明书 NO.11 /* */* * 得到两点节点之间的权重* * param map * param preNode * param node * return */ public static int getWeight(int preNode, int node) if (map != null) for (Side s : map) if (s.getPreNode() = preNode & s.getNode() = node) return s.getWeight(); return -1; /* */* * 从蓝点集合中找出路径最小的那个节点* * param map * param blueAgg * return */ public static MinShortPath getMinSideNode() MinShortPath minMsp = null; if (blueAgg.size() 0) int index = 0; for (int j = 0; j blueAgg.size(); j+) MinShortPath msp = getMinPath(blueAgg.get(j); if (minMsp = null | msp.getWeight()!=-1 & msp.getWeight() minMsp.getWeight() minMsp = msp; index = j; blueAgg.remove(index); return minMsp; /* */* * 得到某一节点的最短路径(实际上可能有多条,现在只考虑一条) * param node 沈 阳 大 学课程设计说明书 NO.12* return */ public static MinShortPath getMinPath(int node) MinShortPath msp = new MinShortPath(node); if (parents != null & redAgg != null) for (int i = 0; i -1) int weight = getWeight(parent, curNode); if (weight -1) tempMsp.addNode(parent); tempMsp.addWeight(weight); curNode = parent; parent = getParent(parents, parent); else break; if (msp.getWeight() = -1 | tempMsp.getWeight()!=-1 & msp.getWeight() tempMsp.getWeight() msp = tempMsp; return msp; /* */* * 图中的有向边，包括节点名及他的一个前向节点名，和它们之间的权重* */class Side private int preNode; / 前向节点 private int node;/ 后向节点 private int weight;/ 权重 public Side(int preNode, int node, int weight) this.preNode = preNode; this.node = node; this.weight = weight; public int getPreNode() return preNode; public void setPreNode(int preNode) 沈 阳 大 学课程设计说明书 NO.13 this.preNode = preNode; public int getNode() return node; public void setNode(int node) this.node = node; public int getWeight() return weight; public void setWeight(int weight) this.weight = weight; class MinShortPath private ArrayList nodeList;/ 最短路径集 private int weight;/ 最短路径 public MinShortPath(int node) nodeList = new ArrayList(); nodeList.add(node); weight = -1; public ArrayList getNodeList() return nodeList; public void setNodeList(ArrayList nodeList) this.nodeList = nodeList; public void addNode(int node) if (nodeList = null) nodeList = new ArrayList(); nodeList.add(0, node); public int getLastNode() int size = nodeList.size(); return nodeList.get(size - 1); public int getWeight() return weight; public void setWeight(int weight) this.weight = weight; 沈 阳 大 学课程设计说明书 NO.14 public void outputPath() outputPath(-1); public void outputPath(int srcNode) String result =; if (srcNode != -1) nodeList.add(srcNode); for (int i = 0; i nodeList.size(); i+) result += + nodeList.get(i); if (i nodeList.size() - 1) result += ,; result += : + weight; System.out.println(result); public void addWeight(int w) if (weight = -1) weight = w; else weight += w; 3.3设计结果输出 图4 输出结果 沈 阳 大 学课程设计说明书 NO.15最小生成树如图图5最小生成树图3.4 设计结果与分析根据Java的知识，将用D算法求最短路径得程序写出，当分别输入1到25时，通过运行得出运行结果图，通过这个图我们可以看出，节点1到节点2的最短路径为2，路径为1、2。节点1到节点3的最短路径为1，路径为1、3。节点1到节点4的最短路径为1，路径为1、4。节点1到节点5的最短路径为4，路径为1,6,5。节点1到节点6的最短路径为3，路径为1、6。4、设计体会 通过本次课程设计，我们对上课所学得知识进行了巩固，对最小生成树、最短路径、Dijkstra算法，最短路由有了更深得理解。本次课程实验，要了解最短得路由得算法，掌握，基本原理和思想。加深对通信网基础这门课程的理解，并且在Dijkstra算法下进行运行，得到输出结果图，并对图进行结果与分析。这次课程设计时间紧任务重，在刚开始的时候手忙脚乱，不知道要做什么，怎么去做，基本是基本是毫无头绪，经过上网查找资料，向同学寻求帮助，最终决定用java来实现实现最短路径Dijkstra算法。通过这次设计，我对java和最短路径算法进行了重新 沈 阳 大 学课程设计说明书 NO.16的认识，基本了解了最短路径算法的工作原理及java的一些编程，进一步学会通过应用软件来实现通信系统的设计，对以后的学习和工作起到了一定的作用，加强了动手能力和专业学习的学业技能。我感触最深的当属查阅了很多网上的设计书和指导书。为了让自己的设计更加完善，查阅相关的资料和借取资料是必不可少的。但是由于本人掌握的相关知识太少，致使课程设计会有很大的缺点，但是我已经尽力了。最后的总体来说，这次课程设计使我受益匪浅。在摸索程序编程问题的过程中，特别有趣，培养了我的设计思维，增强了操作能力。5、参考文献1陈磊,邹林达.Java程序设计M.北京：高等教育出版社，2013-11 2谢希仁.计算机网络M.第五版.北京：电子科技出版社，2006-83 吴秀芹，张洪岩等通信网基础M第一版. 北京：清华大学出版社，2007-5-44 束金龙，闻人凯算法与最短路径M北京：科学出版社，20035 马进通信网分析M北京：人民交通出版社，20036王晓军