图算法问题

Question

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

我不是在寻找最短路径或类似的东西。相反，我只想知道我仍然可以在图表上绘制哪些路径而不会导致循环/循环。例如

L4

可以转到

L1, L2, L5

并且

L2

可以转到

L5

...等等....

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

Answer 1

像 Bellman-Ford 或 Dijkstra 这样的最短路径算法具有告诉您从给定节点“A”可以到达哪些节点的副作用——这正是边 to“A”将到达的节点列表形成一个循环。

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

Answer 2

看看福特算法

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

享受吧，

Answer 3

以下不是答案，只是思考这个问题的一种方式。
你可以从反面思考问题。找到所有恰好缺少一条边的路径来形成一个循环（我没有想到，如何）。那么那些缺失的边缘就不是你正在寻找的边缘。接受除此之外的一切。

Answer 4

要为每个顶点找到不会导致循环的所有可用路径，您可以使用深度优先搜索 (DFS) 来探索所有可能的路径，同时跟踪访问过的顶点以避免循环。如果您需要查找图中的所有路径，另一种方法是 Floyd-Warshall 算法。有关实现这些算法的详细说明和个性化学术帮助，您可以访问https://nerdovo.com/。