Какая есть не очень сложная библиотека для Python, в которой реализованы алгоритмы поиска кратчайшего (самого длинного) пути на графах?
1 ответ
Как @MBo указал в комментарии - NetworkX одна из самых распространенных библиотек в Python для работы с различными видами графов.
Пример:
import networkx as nx
DG = nx.DiGraph()
DG.add_edge('S', 'a', weight=1)
DG.add_edge('a', 'b', weight=1)
DG.add_edge('a', 'c', weight=2)
DG.add_edge('b', 'd', weight=1)
DG.add_edge('b', 'e', weight=2)
DG.add_edge('c', 'e', weight=3)
DG.add_edge('c', 'f', weight=2)
DG.add_edge('d', 'T', weight=1)
DG.add_edge('e', 'T', weight=1)
DG.add_edge('f', 'T', weight=1)
визуализация графа:
nx.draw_networkx(DG)
кратчайший путь:
In [57]: nx.shortest_path(DG, 'S', 'T')
Out[57]: ['S', 'a', 'b', 'd', 'T']
самый длинный путь:
In [61]: nx.dag_longest_path(DG, weight='weight')
Out[61]: ['S', 'a', 'c', 'e', 'T']