我只是为这个问题请求 pseudo code . 我不需要实际的代码 . 只是练习一些图算法 .

问题:假设我们有一个在顶点之间具有严格正边权重的有向图G,非空集A(特殊顶点)使得A是V的子集,其中V是顶点,正整数C和起始顶点S . 找到从S开始并在A中包含 at least C顶点的最短路径(循环OK) . 如果不存在路径,则输出-INF或INF . 仅限多项式时间算法(在V,E和C中) .

我的尝试:如果A中至少有我想要找到的C顶点,那么也许我可以复制图形C次,其中每个复制的图形就像一个层 . 所以当运行Dijkstra时,如果我进入一个特殊的顶点,那个顶点将我连接到下一层的对应物 . 如果图中有10个顶点,并且我想在我进入特殊顶点3次时找到,那么将有30个总顶点,因为每个图层包含相同的10个顶点 .

我有问题将这个想法转换为任何类型的(伪)代码 . 也许我的想法甚至无效,在这种情况下,任何帮助都会在不同解决方案的提案中受到赞赏 .

谢谢 .