1

Какая есть не очень сложная библиотека для Python, в которой реализованы алгоритмы поиска кратчайшего (самого длинного) пути на графах?

1
  • 1
    networkx........
    – MBo
    Commented 15 апр. 2018 в 12:39

1 ответ 1

2

Как @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']
0

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.