K самых длинных путей в DAG - PullRequest
Новая
       84

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

0 голосов
/ 01 мая 2018

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

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

1 Ответ

0 голосов
/ 01 мая 2018

Попробуйте 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 кратчайших путей

...