权值为非负整数的稀疏图的高效APSP算法

摘要：

稀疏图是网络研究中常用的数学模型。本文提出了计算非负整数权稀疏图的所有结点之间最短路径(APSP)的高效算法，在与网络相关的研究中，该算法对于揭示网络的拓扑结构具有较重要的意义。对于一个包含n个结点和m个弧段的非负整数权图，该算法计算所有结点之间最短路径的时间复杂度是O(mn+nC) ，其中C是弧段的最大权值。

关键词： 计算机网络 最短路径 拓扑结构 APSP算法

作者: 黄跃峰 钟耳顺

会议类型: 国内会议

会议名称: 中国测绘学会第九次全国会员代表大会

会议地点: 大连

会议语种:中文

页码: 564-571

在线出版日期: 2009-12-05（万方平台首次上网日期，不代表论文的发表时间）