有没有人知道如何在图中找到特定权重下从源顶点到目标顶点的所有路径?
PS,在我的例子中,图很大(大约百万个顶点),但也希望有一个通用的高效算法。
请不要说要运行 Yen 的算法并搜索“正确的”k。
谢谢。
最佳答案
有一个answer on mathoverflow用于查找无向图中的所有路径。您可以修改此答案以包括重量考虑。正如他在回答中所说的那样
The idea is very simple: Do an exhaustive search, but bail early if you've gotten yourself into a corner.
除此之外,当体重超出限制时,您将不得不放弃。
关于algorithm - 在图中查找特定权重下的所有路径,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20350872/