Dex*_*ers 8 algorithm cyclic directed-acyclic-graphs
我想将循环图转换为非循环图。有没有可以做到这一点的伪代码？我确实尝试过搜索，但大多数都返回了基于马尔可夫链或研究文章的数学位置。
我想编写一个程序来做到这一点，任何方向都会有用。例如考虑下图。
A->B
B->C
C->A
我在麻省理工学院的一次讲座中看到了一个解决方案，但该讲座参考了之前教过的内容而略读了一遍，无法理解。简而言之，它以某种方式复制层中的节点，即最终图表示DAG但传达相同的路径信息。
[见 46:59]
https://www.youtube.com/watch?v=OQ5jsbhAv_M
编辑：
我想对一个循环图问题应用动态规划，例如）说最短路径问题Delta(S,D) where S-> Source node and D->Destination node。由于循环图上的 DP 是无限算法，我们首先需要将循环图转换为无环图，然后对其应用动态规划技术。
我相信您指出了错误的视频，这里是 (46:59)：https://www.youtube.com/watch?v=OQ5jsbhAv_M
这里公开的想法是制作图表的多个副本并将它们排列成层。每一条都代表给定时间图的状态，并且对于遍历的每一条边，您都会向下一层。我没有找到伪代码，但这里详细介绍了执行此操作的方法：https ://cstheory.stackexchange.com/questions/14591/combinatorics-of-bellman-ford-or-how-to-make-无环循环图