《北京邮电大学复杂网络论文》由会员分享，可在线阅读，更多相关《北京邮电大学复杂网络论文（6页珍藏版）》请在金锄头文库上搜索。
1、基于图论和复杂网络知识的最小代价问题摘要：本文结合了图论知识和复杂网络知识来分析网络中的最小代价问题，运用了 Dijkstra 算法和 Floyd算法求解网络的最短路径，运用 Prim 算法和 Kruskal 算法求解网络的最小生成树，并给出了具体的代码实现。关键词：图论；复杂网络；最小代价Minimum Cost Problem Based On Graph Theory and Complex NetworksAbstract: In this paper, the minimum cost problem of networks was analyzed by the knowledge
2、 of graph theory and complex networks. We use two algorithms, Dijkstra algorithm and Floyd algorithm, to find the shortest path of networks, also use two algorithms, Prim algorithm and Dijkstra algorithm, to find the minimum spanning tree of networks. The specific codes are given to implement it.Key
3、 words: graph theory; complex networks; minimum cost1 概述及研究背景1.1 图论与网络网络研究已经成为当今自然科学和社会科学诸多研究领域研究的热点之一。广义地说，网络就是各种类型相互作用事物的整体 1。可以说，整个自然界或人类社会，或两者的综合即整个世界，都是多层次、多类型、多姿态的复杂网络结构 2。事实上，图论知识与网络有着天然的联系。在数学和自然科学领域，网络经常被抽象为许多节点和连接节点之间的边，其中节点用来代表真实系统中的个体或元素，而边则用来表示个体或元素之间的关系，通常是当两个节点之间具有某种特定的关系时连一条边，反之则不连边。
4、有边相连的两个节点在网络中被看作是相邻的。例如，神经系统可以看作是大量神经细胞通过神经纤维相互连接形成的网络 3；计算机网络可以看作是计算机通过通信介质（如光缆、双绞线、同轴电缆）相互连接形成的网络等等。1.2 研究背景研究复杂网络的主要目标之一就是理解并掌握复杂网络上的传播行为，如信息传播问题。信息传播问题的实际意义或实际应用是多方面的，其中之一是以最小传播代价进行传播的问题，例如信件传送、管道铺设和路线设计等问题均需要求以最小的代价来解决问题，或是用最短路径完成任务。本文主要对此进行讨论。2 最短路径求解及算法实现求解两点之间的最短路径是实际应用中的常见问题，也可以转换为图论和网络知识的应
5、用问题。这类问题包括两个典型的问题： 从单个节点到其余各节点之间的最短路径。 各节点之间的最短路径。下面对以上两个问题进行简要讨论。2.1 网络最短距离网络的平均最短距离定义为网络中任意一对节点之间的最短距离的平均值，数学表达式为： 1()ijijGddN其中 dij 为节点 i,j 之间的最短路径长度。大多数真实网络具有较小的平均最短距离。在网络中，从一个节点到另一个节点所需要经过的最大步数叫做这个网络的直径。动态规划中最短路径问题是一种最优化问题，是网络分析中的一个基本问题。它直接应用于解决生产实际的问题，如管道铺设、线路安排和厂区布置等。例如一个实际问题为：给出一个连接若干个城镇的铁路网
6、络，在这个网络的两个指定城镇间找一条最短铁路线。以各城镇为图 G 的顶点，两城镇间的直通铁路为图 G 相应两顶点间的边，得到图G。对 G 的每一边 e 赋以一个实数 w(e)，即直通铁路的长度，称为 e 的权，得到赋权图 G。G 的子图的权是指子图各边的权和。问题即为求赋权图 G中指定的两个顶点 u0,v0 间的最小权的铁路，这段铁路叫做 u0,v0 间的最短路径，它的权叫做 u0,v0 间的距离。现实中这类问题比较常见，这是简单的最短距离问题。2.2 某个节点到其余各节点的最短路径 4在有向图中，寻找从某个节点（称为源点）到其余各个节点或者每一对节点之间的最短带权路径的运算，称为最短路径问题
7、，求解最短路径可以使用 Dijkstra 算法。Dijkstra 算法是解决关于带权图的最短路径问题的一种算法，它要一个个地找出从源节点出发到所有其他节点的最短路径。该算法的基本思想是按最短路径长度不减的次序求解各节点的解，即按由近到远的次序求解各节点的解。不妨假设源节点为 v0。事实上，其求解方法是由部分已知的距 v0 近的节点逐渐向远的节点推进求解的，具体求解方法如下（为便于描述，分别用数组元素 pathv和 distv表示从节点 v0 到节点 v的最短路径及其对应长度）： 初始化：对 v0 以外的各节点 vi，若存在，则将作为 v0 到 vi 的最短路径（当然这只是暂时的）存放到 pat
8、hvi中，同时将其权值作为对应的路径长度存放到 distvi中；否则，分别将空路径“()”和作为 pathvi和 distvi的值。 从未解节点中选择一个 dist 值最小的节点v，则当前的 pathv和 distv就是节点 v 的最终解（从而使 v 成为已解节点） 。 由于某些节点经过 v 可能会使得从 v0 到该节点更近一些，因此应修改这些节点的路径及其长度值，即要修改其 path 和 dist 的值（显然，这些节点既可能是 v 的直接后继，也可能是 v 的间接后继，但我们只需修改其直接后继的 path 和 dist 值即可） 。 重复、，直至所有节点求解完毕。Dijkstra 算法的实现
9、如下：void graph:dijkstra(int v0) /按照Dijkstra算法求解从v0到各节点的最短路径int w,v;for(i=1;i=n;i+) /设置各节点的求解标志solvedi=FALSE;solvedv0=TRUE; /设置v0为已解节点for(i=1;i=n;i+) /初始化源点到各节点的最短路径及其长度if(g.edge_weight(v0,i)!=)disti=g.edge_weight(v0,i);pathv0i=(v0,i);else disti=;pathi=(); for(i=1;in;i+) /控制n-1次循环min=; /在未解节点中搜索最近的节点v
10、for(j=1;j=n;j+)if(solvedj=FALSE & distjmin) min=distj;v=j; solvedv=TRUE; /设置搜索到的当前最短的未解节点为已解节点for(w=g.firstadj(v);w!=0;w=g.nextadj(v,w) /修改v的后继的路径及其长度if(distv+g.edge_weight(v,w)distw)distw=distv+g.edge_weight(v,w); /修改v的dist值pathw=pathv+(v,w); /修改v的path值2.3 每一对节点之间的最短路径 4计算赋权图中各对顶点之间的最短路径，显然可以调用 Dij
11、kstra 算法，具体方法是：每次以不同的节点作为源点，用 Dijkstra 算法求出从该源点到其余节点的最短路径，反复执行 n 次这样的操作，就可以得到从每一个节点到其他节点的最短路径。这种算法的时间复杂度为 O(n3)。Floyd 提出了另外一种更为直接的求解方法，称为 Floyd 算法。假设图 G 的邻接矩阵为 A0，用来存放各边长度： 110nnaKMOL其中：aii=0，i=1,2, ,n；aij=，i,j 之间没有边，在程序中以各边都不可能达到的充分大的数代替；aij=wij，w ij 是 i,j 之间边的长度，i,j=1,2,n。对于无向图，A 0 是对称矩阵， aij=aji。
12、Floyd 算法的基本思想是：递推产生一个矩阵序列 A0,A1,Ak,An，其中 Ak(i,j)表示当从节点vi 到 vj 的路径上所经过的所有节点的序号不大于 k时的最短路径的长度。由这一定义可知，A 0 为图的邻接矩阵，而 An(i,j)则表示从节点 vi 到 vj 的路径上可以经过图中任意节点时的最短路径长度。显然，An 就是所要求的最终的最短路径长度，与此同步地求出相应的最短路径即实现了问题的求解。因此，下面先讨论这一矩阵序列的求解。为求解矩阵序列，可采用递推的方式，即通过依次由矩阵 Ak-1 求解出 Ak 来实现求解（k=1,2,n）。而由 Ak-1 求 Ak，需要逐个求出其中的元素
13、 Ak(i,j)。分析如下：(1) 元素 Ak(i,j)的求解由于在 Ak-1 中的 Ak-1(i,j)表示在从节点 vi 到 vj的路径上所经过的节点序号不大于 k-1 时的最短路径的长度，而 Ak(i,j)则表示在从节点 vi 到 vj 的路径上所经过的节点序号不大于 k 时的最短路径的长度，因此 Ak(i,j)的求解与 Ak-1 相关，根据经过节点 k 是否更近分为两种情况：经过节点 k 更近：即从节点 vi 到 k 再到 vj更近，其中从节点 vi 到 k 以及 k 到 vj 的最短路径上的节点序号均不大于 k-1，因而其最短路径长度值应分别是 Ak-1 中的 Ak-1(i,k)和 A
14、k-1(k,j)。因此在这种情况下，A k(i,j)= Ak-1(i,k)+ Ak-1(k,j)。经过节点 k 反而更远：在这种情况下，Ak(i,j)= Ak-1(i,j)。由此可得由矩阵 Ak-1 求矩阵 Ak 中的元素 Ak(i,j)的操作的伪指令如下：if(Ak-1(i,k)+Ak-1(k,j)Ak-1(i,j)Ak(i,j)=Ak-1(i,k)+Ak-1(k,j);else Ak(i,j)=Ak-1(i,j)(2) 矩阵 Ak 的求解由此可得到整个矩阵 Ak 的求解。由于在求得矩阵 Ak 后，矩阵 Ak-1 已经不再需要，因此，在编写代码时，各矩阵共用一个数组 A 就可以了。(3) F
15、loyd 算法让 k 依次取 1 到 n 求解 Ak 就实现了对整个矩阵序列的求解，由此得 Floyd 算法如下：输入：A 是图 G 的邻接矩阵。输出：path 和 A 分别是各点之间的最短路径及相应的长度。void graph:floyd(adjmatrix& A,adjmatrix& path) /Floyd算法for(i=1;i=n;i+) /初始化路径矩阵pathfor(j=1;j=n;j+)if(Aij!=)pathij=(i,j);else pathij=();for(k=1;k=n;k+) /控制Ak的求解for(i=1;i=n;i+) /求解Ak(i,j)for(j=1;j=n;j+)if(Aik+AkjAij)Aij=Aik+Akj;pathij=pathik+pathkj;3 最小生成树求解及算法实现下面先从一个实例开始本部分的内容。假设在某地有一个煤气供应站点及 n-1 个生活小区，现在要给这些小区铺设煤气管道。请
