Эффективный кратчайший путь в DAG с помощью графического инструмента Python - PullRequest
Новая
       13

Эффективный кратчайший путь в DAG с помощью графического инструмента Python

0 голосов
/ 21 января 2019

Задача: Я хочу вычислить кратчайший путь между исходным и целевым узлами в группе DAG (направленный ациклический граф), используя graph-tool Python эффективно . Мой DAG имеет отрицательный вес.

Теоретически, это вычислительно «простая» проблема (т. Е. O (V + E) ), сначала вычисляющая топологическую сортировку графа, а затем посещающая и обновляющая родительские узлы и расстояния (например, как обсуждено здесь ).

Как я могу эффективно реализовать это, используя graph-tool?

Мои неудачные попытки до сих пор:

  • ручная реализация теоретически эффективного алгоритма в Python. Однако, поскольку мне приходится перебирать каждую вершину в графе, это становится неприемлемо медленным
  • использование функции shortest_path из graph-tool для вызова подпрограммы Dijkstra из Boost Graph Library будет иметь приемлемое время выполнения, но не полностью использует структуру DAG и в любом случае не работает для отрицательных весов
  • использование shortest_path для вызова Bellman-Ford возвращает правильный кратчайший путь, но не использует структуру DAG и является слишком медленным ( O (VE) ).

Эффективный алгоритм кратчайшего пути DAG реализован как dag_shortest_paths в базовой Boost Graph Library . Есть ли какой-нибудь способ доступа к этой функции через graph-tool или любой другой способ ее эффективного вычисления с помощью graph-tool?

Ответы [ 2 ]

0 голосов
/ 27 января 2019

Эта функциональность была добавлена ​​в git-версию Graph-Tool:

https://git.skewed.de/count0/graph-tool/commit/012787ecde818efc2b893ad0d8aff819b8deb6ca

Необязательный параметр dag=True теперь может быть передан в shortest_path(), который достигает того, что выхочу.

0 голосов
/ 21 января 2019

Вы пытались использовать библиотеку Networkx? Так как я знаю, это эффективно, работает для взвешенных и невзвешенных графиков, и его очень просто использовать.

https://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.algorithms.shortest_paths.weighted.all_pairs_dijkstra_path.html#networkx.algorithms.shortest_paths.weighted.all_pairs_dijkstra_path

Пример: 

    >>> import networkx as nx

    >>> G=nx.path_graph(5)
    >>> path=nx.all_pairs_dijkstra_path(G)
    >>> print(path[0][4])

[0, 1, 2, 3, 4]
...