北京邮电大学复杂网络论文

《北京邮电大学复杂网络论文》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、基于图论和复杂网络知识的最小代价问题摘要：本文结合了图论知识和复杂网络知识来分析网络中的最小代价问题，运用了Dijkstra算法和Floyd算法求解网络的最短路径，运用Prim算法和Kruskal算法求解网络的最小生成树，并给出了具体的代码实现。关键词：图论；复杂网络；最小代价MinimumCostProblemBasedOnGraphTheoryandComplexNetworksAbstract:Inthispaper,theminimumcostproblemofnetworkswasanalyzedbytheknowle

2、dgeofgraphtheoryandcomplexnetworks.Weusetwoalgorithms,DijkstraalgorithmandFloydalgorithm,tofindtheshortestpathofnetworks,alsousetwoalgorithms,PrimalgorithmandDijkstraalgorithm,tofindtheminimumspanningtreeofnetworks.Thespecificcodesaregiventoimplementit.Keywords:graph

3、theory;complexnetworks;minimumcost1概述及研究背景1.1图论与网络网络研究已经成为当今自然科学和社会科学诸多研究领域研究的热点之一。广义地说，网络就是各种类型相互作用事物的整体[1]。可以说，整个自然界或人类社会，或两者的综合即整个世界，都是多层次、多类型、多姿态的复杂网络结构[2]。事实上，图论知识与网络有着天然的联系。在数学和自然科学领域，网络经常被抽象为许多节点和连接节点之间的边，其中节点用来代表真实系统中的个体或元素，而边则用来表示个体或元素之间的关系，通常是当两个节点之间具有某种特定的

4、关系时连一条边，反之则不连边。有边相连的两个节点在网络中被看作是相邻的。例如，神经系统可以看作是大量神经细胞通过神经纤维相互连接形成的网络[3]；计算机网络可以看作是计算机通过通信介质（如光缆、双绞线、同轴电缆）相互连接形成的网络等等。1.2研究背景研究复杂网络的主要目标之一就是理解并掌握复杂网络上的传播行为，如信息传播问题。信息传播问题的实际意义或实际应用是多方面的，其中之一是以最小传播代价进行传播的问题，例如信件传送、管道铺设和路线设计等问题均需要求以最小的代价来解决问题，或是用最短路径完成任务。本文主要对此进行讨论。2最短

5、路径求解及算法实现求解两点之间的最短路径是实际应用中的常见问题，也可以转换为图论和网络知识的应用问题。这类问题包括两个典型的问题：①从单个节点到其余各节点之间的最短路径。②各节点之间的最短路径。下面对以上两个问题进行简要讨论。2.1网络最短距离网络的平均最短距离定义为网络中任意一对节点之间的最短距离的平均值，数学表达式为：其中dij为节点i,j之间的最短路径长度。大多数真实网络具有较小的平均最短距离。在网络中，从一个节点到另一个节点所需要经过的最大步数叫做这个网络的直径。动态规划中最短路径问题是一种最优化问题，是网络分析中的一个

6、基本问题。它直接应用于解决生产实际的问题，如管道铺设、线路安排和厂区布置等。例如一个实际问题为：给出一个连接若干个城镇的铁路网络，在这个网络的两个指定城镇间找一条最短铁路线。以各城镇为图G的顶点，两城镇间的直通铁路为图G相应两顶点间的边，得到图G。对G的每一边e赋以一个实数w(e)，即直通铁路的长度，称为e的权，得到赋权图G。G的子图的权是指子图各边的权和。问题即为求赋权图G中指定的两个顶点u0,v0间的最小权的铁路，这段铁路叫做u0,v0间的最短路径，它的权叫做u0,v0间的距离。现实中这类问题比较常见，这是简单的最短距离问题

7、。2.2某个节点到其余各节点的最短路径[4]在有向图中，寻找从某个节点（称为源点）到其余各个节点或者每一对节点之间的最短带权路径的运算，称为最短路径问题，求解最短路径可以使用Dijkstra算法。Dijkstra算法是解决关于带权图的最短路径问题的一种算法，它要一个个地找出从源节点出发到所有其他节点的最短路径。该算法的基本思想是按最短路径长度不减的次序求解各节点的解，即按由近到远的次序求解各节点的解。不妨假设源节点为v0。事实上，其求解方法是由部分已知的距v0近的节点逐渐向远的节点推进求解的，具体求解方法如下（为便于描述，分别用

8、数组元素path[v]和dist[v]表示从节点v0到节点v的最短路径及其对应长度）：①初始化：对v0以外的各节点vi，若存在，则将作为v0到vi的最短路径（当然这只是暂时的）存放到path[vi]中，同时将其权值作为对应的路径长度存