K самых длинных путей в DAG

Я хочу найти K самых длинных путей в направленном ациклическом графе (DAG). Я прочитал несколько статей об этом, но я не смог найти никакого фактического кода, который его реализовал. Может ли кто-нибудь помочь мне с python или псевдокодом?

Вот одно интересное объяснение алгоритма: https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3009499/


python algorithm shortest-path longest-path viterbi
person Sina Faezi    schedule 30.04.2018    source источник
comment
Это вряд ли будет самым быстрым, но очень простым в реализации: используйте Floyd-Washall для всех пар кратчайших путей с отрицанием всех весов ребер. Затем найдите в результате самые отрицательные длины пути.   -  person Gene    schedule 01.05.2018
comment
Сина, похоже, статья посвящена поиску наиболее вероятных путей HMM, а не самых длинных.   -  person Serge    schedule 01.05.2018

Ответы (1)


arrow_upward
0
arrow_downward

Попробуйте https://baoilleach.blogspot.ca/2013/11/the-shortest-route-to-longest-path.html

Также вы можете инвертировать веса и применить какой-либо существующий пакет для k кратчайших путей во взвешенном графе, при условии, что отрицательные веса поддерживаются.

Если отрицания не поддерживаются, вы можете прибегнуть к перезаписи веса графика, как в алгоритме Джонсона (см. Википедию или/и https://www.researchgate.net/publication/275645125_Weighted_graph_algorithms_with_Python, а затем применить k кратчайших путей, скажем, Python Dijkstra k кратчайших путей

person Serge    schedule 01.05.2018
comment
Алгоритм Дейкстры не работает для отрицательных весов ребер. - person user2357112 supports Monica; 01.05.2018
comment
объяснил, как переписать веса для алгоритма Дейкстры - person Serge; 01.05.2018