|
|||||
|
|
| 结点数受限的最短路径计数问题 | |
| 引用本文： | 何建军.结点数受限的最短路径计数问题[J].教育技术导刊,2016,15(4):28-31. |
| 作者姓名： | 何建军 |
| 作者单位： | 重庆大学城市科技学院 电气信息学院，重庆 402167 |
| 摘 要： | 受顶点数限制的最短路径计数问题在复杂性网络的社区识别、介数计算等方面有重要应用，但目前对其研究较少。Bellman算法能有效解决边带有负权且无负圈的最短路径问题，但对结点数受限定的最短路径的计数问题，直接用Bellman公式进行求解，则存在重复计数的问题。对Bellman递推关系式进行改进，建立新的求结点数受限制的最短路径的递推关系式和求结点数受限制的最短路径数目的递推关系式，从而给出了结点数受限定的最短路径计数问题的一种求解算法，并验证了其正确性。 |
| 关 键 词： | 最短路径 时间复杂度 空间复杂度 |
| 点击此处可从《教育技术导刊》浏览原始摘要信息 | |
| 点击此处可从《教育技术导刊》下载免费的PDF全文 | |