小编Phi*_*ill的帖子

通过图表在有效时间内找到最短路径,其中附加约束条件路径必须包含n个节点.

我们有一个有向加权图.它可能包含也可能不包含循环.我们可以使用Dijkstra算法轻松找到最短路径,但Dijkstra不能保证边缘数量.

我们能想到的最好的方法是保留一个节点的最佳n路径列表,但这比vanilla Dijkstra的内存使用了大量内存.