DAG中的K条最长路径

Question

我想在有向无环图（DAG）中找到K条最长路径。我读过一些关于它的文章，但是我找不到任何实现它的实际代码。有人能帮我用python或伪代码吗？在

下面是一个有趣的算法解释： https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3009499/

Answer 1

尝试https://baoilleach.blogspot.ca/2013/11/the-shortest-route-to-longest-path.html

你也可以对权重取反，并对加权图中的k条最短路径应用一些现有的包，允许负权重。在

如果不支持否定，则可以像Johnson算法那样重新编写图的权重（参见wikipedia或/和https://www.researchgate.net/publication/275645125_Weighted_graph_algorithms_with_Python），然后应用k条最短路径，比如Dijkstra的Python Dijkstra k shortest paths