顶点数最大的最短路径

Question

我想找到两个顶点之间有最短约束的最短路径：最多可以访问n个顶点。该图是有向图，连接图，非负图，可能包含循环。

例：

1. 最短路径0-> 2与n = 2时是18
2. 最短路径0-> 3与n = 3的是22
3. 最短路径0-> 3与N = 4是9

到目前为止，我已经实现了Djikstras算法来获得最短的最短路径，而我的想法是保持当前访问的顶点的计数，如果超过n，它会往后退一步，然后尝试另一条路径。据我所知，Djikstras不能如这里所述用于回溯。

另一个想法是以某种方式存储表中每个节点之间的每个路径。但我不确定Djikstra如何找到权重为18的0-> 2路径，因为它实际上并不是最短的路径...

有谁知道如何解决这个问题？

Answer 1

将每个顶点划分为多个n顶点，也就是说，对于顶点u，我们创建n表示为的顶点(u, 1) ... (u, n)，第二个数字显示此顶点的步数。对于从u到v的每个边，我们1<=i<=n-1在新图中创建从（u，i）到（v，i + 1）的边。现在，如果要使用n计算u和v之间的最短路径，只需从（u，1）开始Dijkstra，那么答案是min(result (v, i) | 1<=i<=n)

顶点总数可以为n * n，因此复杂度约为 O(n^2*log(n^2))