图算法问题

Question

如何为每个顶点找到不会导致循环的所有可用路径？使用什么算法？请简明扼要，如果可能，请提供链接，如果下面的精彩图表中有不清楚的地方，请提出问题:)

​

我不是在寻找最短的路径或类似的东西。相反，我只想知道我仍然可以在我的图形上绘制哪些路径，而不会导致循环。例如，L4可以转到L1, L2, L5，L2可以转到L5...and，等等。

我想我想要一个有向无环图，并且需要帮助找出使用哪种算法以及如何使用？

Answer 1

看看福特算法

http://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm

享受‘，

Answer 2

像贝尔曼-福特或Dijkstra这样的最短路径算法有一个副作用，就是告诉您可以从给定节点"A“到达哪些节点--这正是从边到 "A”将形成循环的节点列表。

我怀疑有一种方法可以修改Bellman-Ford，以一次性生成所有这些列表，而不是为每个节点单独运行算法，但我将把这留给读者作为练习。:)

Answer 3

以下不是答案，而只是思考这个问题的一种方式。

你可以从相反的角度思考这个问题。找出所有缺少一条边的路径来形成一个循环(我还没有想过它是如何形成的)。那么那些缺失的边就不是你正在寻找的边。接受除此之外的一切。