【摘 要】
：
稀疏图是网络研究中常用的数学模型。本文提出了计算非负整数权稀疏图的所有结点之间最短路径(APSP)的高效算法，在与网络相关的研究中，该算法对于揭示网络的拓扑结构具有较重要的意义。对于一个包含n个结点和m个弧段的非负整数权图，该算法计算所有结点之间最短路径的时间复杂度是O(mn+nC) ，其中C是弧段的最大权值。
【出 处】
：
中国测绘学会第九次全国会员代表大会
论文部分内容阅读
稀疏图是网络研究中常用的数学模型。本文提出了计算非负整数权稀疏图的所有结点之间最短路径(APSP)的高效算法，在与网络相关的研究中，该算法对于揭示网络的拓扑结构具有较重要的意义。对于一个包含n个结点和m个弧段的非负整数权图，该算法计算所有结点之间最短路径的时间复杂度是O(mn+nC) ，其中C是弧段的最大权值。
其他文献
本文针对面向复杂应用任务的遥感信息处理服务选择难题，将服务选择问题转化为面向任务语义的处理服务分类问题，提出一种基于语义信息分类的遥感信息处理服务选择方法。首先根据遥感信息处理服务的多重语义聚类成若干服务簇；其次基于信息熵在处理服务各个属性上的下降速度构建决策树，发现任务语义与处理服务语义之间的层次关联关系，并转换为可以理解的知识形式——服务选择规则；最后将服务选择规则用于服务簇的分类选择。实验结
交通信息服务系统中的动态路况信息服务是研究的热点和难点课题，现有的动态路况信息发布方式受众面广，如果路网中的大部分参与者(能够接收到这些信息的车辆驾驶者)都利用接收到的路况信息实时规划出行路线，则势必对全局交通系统造成较大的扰动，在避开现有交通拥堵点的同时形成新的拥堵点。本文基于GIS空间数据模型和多智能体的理论方法，研究了一种多智能体协作动态路况信息服务技术，通过增强信息提供者和出行者之间的交互
本文针对“面向实体”的数据结构，对国内外现有城市道路交通事故分析模型进行了改进，提出了基于空间计算、动态索引和分类编码的事故分析模型。以武汉市为例建立试验系统研究五年来道路交通事故特点，提出了道路黑点的划分依据，模拟出黑点路段分布的变化轨迹。
本文基于约束三角网探测点线面之间的空间邻近关系。研究首先建立点线面数据点索引，以索引内所有坐标点组成数据集，以线、面为约束条件，构建约束三角网。通过三角网编码，借助数据点索引，探测地理实体间的空间邻近关系。基于空间邻近关系推理，将空间邻近关系分为相邻与相离关系，完成全局性点线面空间邻近关系探测。实验结果表明，该算法简单易行，不局限于某两类地理实体，探测结果符合主观认识，为自动探测地理实体空间邻近关
随着GPS、GIS和RS技术的快速发展，3S技术在第二次土地利用调查中的应用也越来越广泛。RS影像成为了土地利用信息主要的数据源，GPS能在外业调 查中获取更新数据，GIS则成为了内业数据处理和数据分析的主要工具，但是目前对于3S技术应用在第二次土地利用调查中的成果评价还比较少，不利于从技术实施效果的角度来对方法进行改进。本文以基于“3S”的第二次土地利用调查成果评价为研究对象，对影响相关图件，表
地面激光扫描仪作为对地近距离建筑物观测的主要手段之一，已经越来越广泛应用的古建筑保护活动中。点云数据的三角网构建是地面三维激光扫描数据处理的难点，也是后续三维重建的基础。大木结构是古建筑物中比较常见的构件，由于其数据量较大，常用的三角网构建方法难以适应需求。本文在充分分析古建筑物大木结构特点的基础上，将圆柱投影与基于切平面投影法的三角网构建方法进行结合，实现了融合圆柱面和平面投影三角网构 建方法，
本文阐述了非点源污染研究历程和空间信息技术在非点源污染研究中的应用，在此基础上，收集了北京山区的地形、土壤、水系和土地利用等空间信息数据，利用MUSLE方程，在地理信息系统的支持下，得到了北京山区非点源污染风险区分布图，取得了良好结果。结果表明，空间信息技术是进行非点源污染研究的强有力的工具，为非点源污染的管理控制提供了有力支持。
本文利用AMSR-E和modis数据，探讨了微波穿透指数MVI与光学植被指数NDVI的关系。结果表明，两者呈负相关关系，相关系数为-0.463。利用两者关系建立回归方程，并利用MVI数据模拟生成NDVI图像。与真实NDVI图像相比，模拟NDVI图像的精度达到0.626。综合各种因素，这一模拟结果比较令人满意。
许多虚拟现实程序需要模拟物体之间的各种交互。其中一个就是保证物体不被穿透。本文提出一个新颖的算法检测虚拟相机和地形的碰撞。碰撞被检测到后，给出一个良好的碰撞响应。这个算法不需要为物体提前计算包围盒，所以相对于使用球树(使用球作为包围盒)的算法，节省了内存。在一个虚拟全球地形环境程序中测试，这个算法能达到实时速度。经过试验比较这个算法比使用球树的碰撞检测算法大约快几十倍。
“煤航”原名为煤炭部航测大队，成立于1965年7月，是我国较早从事航测成图的单位之一，尤其是在1978年至1982年间，煤炭部投入大量外汇先后从瑞士、德国引进40多套航测成图设备，使煤航成为当时全国设备数量最多、生产能力最大的航测成图单位。近年来，测绘行业、测绘技术发生了较大变化，原煤炭部航测大队也发展成为以航测成图为主业，航空摄影、遥感地质、地图制印、地下管线探测、地理信息技术等全面发展的空间信