结点数受限的最短路径计数问题

• 作者: 何建军
• 来源期刊: 软件导刊
• 学科: 工学
• 关键词: 最短路径 时间复杂度 空间复杂度
• 年，卷（期）: 2016,（4）
• 所属期刊栏目: 软件理论与方法
• 页码范围: 28-31
• 页数: 4页
• 分类号: TP301.5
• 字数: 6442字
• 语种: 中文
• DOI: 10.11907/rjdk.1511568

摘要

受顶点数限制的最短路径计数问题在复杂性网络的社区识别、介数计算等方面有重要应用,但目前对其研究较少.Bellman算法能有效解决边带有负权且无负圈的最短路径问题,但对结点数受限定的最短路径的计数问题,直接用Bellman公式进行求解,则存在重复计数的问题.对Bellman递推关系式进行改进,建立新的求结点数受限制的最短路径的递推关系式和求结点数受限制的最短路径数目的递推关系式,从而给出了结点数受限定的最短路径计数问题的一种求解算法,并验证了其正确性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	何建军	重庆大学城市科技学院电气信息学院	10	267	6.0	10.0