-2

我想在有向无环图(DAG)中找到 K 条最长的路径。我已经阅读了几篇关于它的文章,但我找不到任何实现它的实际代码。有人可以帮助我使用python或伪代码吗?

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

4

1 回答 1

0

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

您也可以否定权重并为加权图中的 k 最短路径应用一些现有的包,支持授予的负权重。

如果不支持负数,您可以像在约翰逊算法中那样使用图形权重重写(参见维基百科或/和https://www.researchgate.net/publication/275645125_Weighted_graph_algorithms_with_Python,然后应用 k 最短路径,例如 Dijkstra 的 Python Dijkstra k 最短路径

于 2018-05-01T02:42:16.790 回答