算法惊魂：寻找图中长度为K的路径数的O(EV+VlogVlogK)解法
2025-08-25
本文探讨了一个看似简单的算法问题：在有向无权图中，从节点A到节点B长度为K的路径有多少条？文章从简单的BFS和动态规划算法出发，逐步深入，引入了矩阵幂运算、线性递推、生成函数、消元多项式和Berlekamp-Massey算法等高级算法，最终给出了一个时间复杂度为O(EV+VlogVlogK)的惊艳解法，远超传统的O(EK)或O(V³logK)算法。作者深入浅出地讲解了这些算法的原理和联系，并用简洁明了的语言阐述了问题的复杂性和求解过程中的精妙之处。
算法
线性递推