在最小总长度的k条路径的图上搜索

DOI:

评审日期

出版日期

注解: 考虑了在加权定向图上搜索从给定初始顶点到具有弧的非负权重的所有其他顶点的最小总长度的k条不相交路径的问题。 结果表明，不可能使用"贪婪"方法，即找到最佳路径，将此路径的顶点与入射弧一起从图中移除并重复搜索。 问题简化为在具有一些附加约束的n^k个顶点的隐式图上找到最短路径，其中n是原始图的顶点数。 隐式图的稀疏性允许使用有理数据结构，降低了寻路算法的复杂度。 描述的算法的软件实现来执行。 在测试过程中，用弧权值生成了完整的图，其中最小总长度的路径由大量弧组成。 出于实际目的和计算能力，k的小值是感兴趣的。 在这种情况下，将k的值视为常数是正确的，并且算法的复杂度由值O(n^(k+1)log n)估计。 所需的内存成本为O(n^k)。 程序在各种测试上的运行时间与所获得的算法复杂性估计值不矛盾。

出版日期: