基于核心路由器的路由选择最优化算法研究与实现毕业论文设计

基于核心路由器的路由选择最优化算法研究与实现毕业论文设计内容摘要：

了 Dijkstra 算法作用于图 中所示的图时各步的状态表，其源顶点是 b。 表 算法运行过程 顶点 遍数 初值 1 2 3 4 5 6 a ∞ 3b √ 3b √ 3b √ 3b √ 3b √ 3b b 0 √ 0 √ 0 √ 0 √ 0 √ 0 √ 0 c ∞ 5b 4a √ 4a √ 4a √ 4a √ 4a d ∞ ∞ ∞ 6c √ 6c √ 6c √ 6c e ∞ ∞ ∞ 8c 8c √ 8c √ 8c f ∞ ∞ ∞ ∞ 11d 9e √ 9e 图 有向图 最初，除顶点 b 的初值为 0 之外，其余各定点的最短路径长度估计值均赋初值为∞，因此在第一遍中可选顶点 b。 表中√表四最短路径已经知道（ truev k ）。 然后，顺着顶点 b 发出的两条边即 b→ a 及 b→ c，并相应地跟新它们的长度估计值。 顶点 a 的新长度为 3，顶点 c 的新长度为 5。 在这两种情况中，最短路径上 a 与 c 的下一个顶点均为 b。 在第二遍中， 选择顶点 a，并在数据项旁边标记 √以表明至它的最短路径长度已经知道，从 a 至 c 有一条边 a→ c。 从 b 开始经过 a 至 c 的长度为 4，由于它小于 b 至 c 的路径长度 5，所以顶点 c 被赋予新的值 4，并把它的前驱赋予路径 a。 按照以上方式进行 n 遍，直至找出所有的最短路径。 图 就是最终结果，它的顶点旁边标有从 b 至 v 的最短路径长度 vd。 每个顶点（除b 外）都只有一条发射边，把它和它的下一个顶点连接起来，逆向构造一条 b 至 v 的最短路径。 图 图 的最短路径图 Dijkstra 算法实现 Dijkstra 算法利用了 TableEntry 数据结构，每个 TableEntry 具有 known、 distance、predecessor 三个域，对应变量 Kv， dv， pv。 首先介绍 Dijkstra 算法的数据结构。 Struct TableEntry { bool known。 int distance。 Vertex::Number predecessor。 TableEntry():known(false),distance(numeric_limitsint::max()){} }。 Class Assoc:public Association { int priority。 public: Assoc(int p,Objectamp。 object):Association(priority,object),priority(p) { rescindOwnership()。 } }。 函数 DijkstraAlogrihm 有两个参数，第一个参数是一个指向有向图实例的 const 型引用，这个有向图是一个边带权图，且权是 int 类型。 第二个参数也是 const 型引用，是一 个指向起始点（顶点）的引用。 Digraphamp。 DijkstraAlgorithm（ Digraph constamp。 g， Vertex constamp。 s） { unsigned int const n=()。 ArrayTableEntrytable(n)。 PriorityQueueamp。 queue=*new BinaryHeap(())。 table[s].distance=0。 (*)new Assoc(0,const_castCertexamp。 (s))。 While(!()) { Assocamp。 assoc=dynamic_castAssocamp。 (())。 Vertexamp。 v0=dynamic_castVertexamp。 (())。 if(!table[v0].known) { Table[v0].known=true。 Iteratoramp。 p=(v0)。 While(!()) { WeightedEdgeamp。 edge=dynamic_castWeightedEdgeamp。 (*p)。 Vertexamp。 v1=()。 intamp。 weight=dynamic_castintamp。 (())。 int const d=table[v0].distance+weight。 if(table[v1].distanced) { table[v1].distance=d。 table[v1].predecessor=v0。 (*new Assoc(d,v1))。 } ++p。 } delete amp。 p。 } delete amp。 assoc。 } delete amp。 queue。 Diraphamp。 result=*new DigraphAsLists(n)。 for(Vertex::Number v=0。 vn。 ++v) (*new WeightedVertex(v,*new int(table[v].distance)))。 for(Vertex::Number v=0。 vn。 ++v) if(v!=s) (*new Edege(result[v],result[table[v],predecessor]))。 return result。 } Kruskal 算法原理 假设 G=(V,E)是一个具有 n 个顶点的边带权无向图， T=（ U,TE）是 G 的最小生成树， U 的初值等于 V，即包含有 G 种的全部顶点， TE的初值为空。 此算法的基本思想是：将图 G 中的边按权值从大道小的顺序依次选取，若选取的边使生成树 T 不形成回路，则把它并入 TE中，保留为 T 的一条边，若选取的边使生成树 T 形成回路，则将其舍弃，如此进行下去，直到 TE 中包含 n1 条边为止，此时的 T 即为最小生成树。 图 是边带权无向图，图 是 Kruskal 算法作用于图 的处理过程。 图 图 Kruskal 算法要计算顶点集 V 的分区 1n,......,2,1,0 PPPP ，最初的分区0P是由 n 个单顶点集构成的，即0P={{ 1V }， { 2V }， …… ,{ 3V } }。 当从边集数组中按次序选取一条边时，若它的两个端点分属于不同的集合，则表明此边联通了两个不同的连通分量，因每个连通分量无回路，所以连通后得到的连通分量仍不会产生回路，此边应保留作为生成树的一条边，同时把端点所长的两个集合合并成一个，即成为一个连通分量；当选取的一条边的两个端点同属于一个集合时，此边应放弃，因同一个集合中的顶点是连通无回路的，若再加入一条边则必产生回路。 在上述离子中， Kruskal 算法计算了下列分区序列： 0P ={{a},{b},{c},{d},{e},{f}} 1P={{a,d},{b},{c},{e},{f}} 2P ={{a,d},{b},{c},{e,f}} 3P ={{a,d},{b},{c,e,f}} 4P ={{a,d,c,e,f},{b}} 5P ={{a,b,c,d,e,f}} Kruskal 算法实现 函数 KruskalAlgorithm 的参数指向带权无向图的 const 型引用。