Menu
毕业论文
计算机论文
经济论文
生物论文
数学论文
物理论文
机械论文
新闻传播论文
音乐舞蹈论文
法学论文
文学论文
材料科学
英语论文
日语论文
化学论文
自动化
管理论文
艺术论文
会计论文
土木工程
电子通信
食品科学
教学论文
医学论文
体育论文
论文下载
研究现状
任务书
开题报告
外文文献翻译
文献综述
范文
中国学术界和华人影视界X度空间理论初探(4)
本文通过构建与计算机学术界和华人影视界同构的计算机模型,模拟两个圈子的社会关系,并利用这些分析各自圈子内社会关系,尝试发现和解释两个圈子的各自组织特点,行为方式,个性特征等,以推进这两个圈子内更好的信息共享和数据合作。
2 课题研究所采用的算法及工具
2.1 相关算法介绍
2.1.1最短路径算法
本次课题中为了计算学术界中任何两个人之间最短距离的平均值,我选用图这种数据结构来构建社交网路,并使用Dijkstra及floyd算法分别进行单源最短路径以及所有点对间最短路径的计算,因此下面简单介绍一下折算法。
Dijkstra算法
Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法。Dijkstra一般的表述通常有两种方式,一种用永久和临时标号方式,一种是用OPEN,CLOSE表的方式,这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权边。其具体原理如下所述。
首先,引进一个辅助向量D,它的每个分量D表示当前所找到的从始点v到每个终点vi的最短路径的长度。如D[3]=2表示从始点v到终点3的路径相对最小长度为2。这里强调相对就是说在算法过程中D的值是在不断逼近最终结果但在过程中不一定就等于最短路径长度。它的初始状态为:若从v到vi有弧,则D为弧上的权值;否则置D为∞。显然,长度为D[j]=Min{D | vi∈V} 的路径就是从v出发的长度最短的一条最短路径。此路径为(v,vj)。那么,下一条长度次短的最短路径是哪一条呢?假设该次短路径的终点是vk,则可想而知,这条路径或者是(v,vk),或者是(v,vj,vk)。它的长度或者是从v到vk的弧上的权值,或者是D[j]和从vj到vk的弧上的权值之和。一般情况下,假设S为已求得最短路径的终点的集合,则可证明:下一条最短路径(设其终点为X)或者是弧(v,x),或者是中间只经过S中的顶点而最后到达顶点X的路径。因此,下一条长度次短的最短路径的长度必是D[j]=Min{D | vi∈V-S} 其中,D或者是弧(v,vi)上的权值,或者是D[k](vk∈S)和弧(vk,vi)上的权值之和。 迪杰斯特拉算法描述如下:1)arcs表示弧上的权值。若不存在,则置arcs为∞。S为已找到从v出发的最短路径的终点的集合,初始状态为空集。那么,从v出发到图上其余各顶点vi可能达到的最短路径长度的初值为D=arcs[Locate Vex(G,v),i] vi∈V 2)选择vj,使得D[j]=Min{D | vi∈V-S} 3)修改从v出发到集合V-S上任一顶点vk可达的最短路径长度。
Floyd算法
Floyd算法是解决图中所有点对间最短路径问题的一个形式简单的算法,它的基本思想是这样的:
假设求从顶点vi到顶顶vj的最短路径。如果从vi到vj有弧,则从vi到vj存在一条长为arcs[i][j]的路径,该路径不一定是最短路径,尚需要n次试探。首先考虑路径(vi,v0,vj)是否存在(即判别弧(vi,v0)和(v0,vj)是否存在)。如果存在,则比较(vi,vj)和(vi,v0,vj)的路径长度并取长度较短者为从vi到vj的中间顶点序号不大于0的最短路径。假如在路径上再增加一个顶点v1,也就是说,如果(vi,…,v1)和(v1,…,vj)分别是当前找到的中间顶点的序号不大于0的最短路径,由此,路径(vi,…,v1,…,vj)就有可能是从vi到vj的中间顶点的序号不大于1的最短路径。将它和已经得到的从vi到vj中间顶点序号不大于0的最短路径比较,从中选出中间顶点的序号不大于1的最短路径之后,再增加一个顶点v2,继续进行试探。依次类推。在一般情况下,若(vi,…,vk)和(vk,…,vj)分别是从vi到vk和从vk到vj的中间顶点的序号不大于k-1的最短路径,则将(vi,…,vk,…,vj)和已经得到的从vi到vj且中间顶点的序号不大于k-1的最短路径相比较,其长度较短者便是从vi到vj的中间顶点的序号不大于k的最短路径。这样,在经过n次的比较之后,最后求得的必是从vi到vj的最短路径。按此方法,可以同时求得所有顶点对之间的最短路径。
共6页:
上一页
1
2
3
4
5
6
下一页
上一篇:
基于Kinect的人体运动姿态捕捉和识别技术研究
下一篇:
社会标签系统挖掘研究中文博客标签及标签云图的自动生成研究
论利用ebXML和SOAP开发Web服务【2352字】
电子政务环境下公务员的...
用VB实现聊天讨论室和点對点會话【671字】
提高实时操作系统的实时...
嵌入式数据库典型技术―...
联结主义的连续记分IRT模...
使用http协议和winsockapi实现...
10万元能开儿童乐园吗,我...
国内外图像分割技术研究现状
AT89C52单片机的超声波测距...
医院财务风险因素分析及管理措施【2367字】
神经外科重症监护病房患...
C#学校科研管理系统的设计
承德市事业单位档案管理...
志愿者活动的调查问卷表
公寓空调设计任务书
中国学术生态细节考察《...