我很难找出一个最短路径算法,如果给定一个起点为a,终点为b的无向无权图,每条路径都必须包含/运行到顶点v。
如果长度大于n/2,是否有可能把它取为o(n)?
我发现了这个,但它没有在我的头脑中点燃任何东西它确实让我想到了bfs,但我怎么知道当我通过顶点v?
有人能给我指个方向吗?
谢谢!

最佳答案

把问题分解成两个子问题:找到一条从a到v的路径,然后找到另一条从v到b的路径。
如果要求整个路径不能重用边或顶点,则需要做一些更详细的工作我现在还不清楚那到底是什么一种可能是在搜索从v到b的路径时删除从a到v的路径中使用的边/顶点(v本身除外)。但这不能保证全局路径最短,因此必须进行一些回溯。但我怀疑有更好的方法。

09-30 14:09
查看更多