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

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

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

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

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

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

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


python graph-tool
person netword    schedule 21.01.2019    source источник

Ответы (2)


arrow_upward
0
arrow_downward

Эта функция была добавлена ​​в git-версию графического инструмента:

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

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

person Tiago Peixoto    schedule 27.01.2019
comment
Спасибо! :) Не могли бы вы прояснить поведение флага negative_weights, если dag=True передается? При пробном запуске вызов shortest_path с dag=True, negative_weights=False выполняется значительно быстрее, чем с dag=True, negative_weights=True, хотя для групп DAG отрицательные веса не должны влиять на время выполнения. - person netword; 28.01.2019
comment
Параметр negative_weights=True запускает алгоритм Беллмана-Форда. При использовании dag=True нет необходимости передавать negative_weights=True. - person Tiago Peixoto; 29.01.2019

arrow_upward
-1
arrow_downward

Вы пробовали использовать библиотеку 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_paths.weighted.all_pairs_dijkstra_pathnofollownoreferrer

Пример:

    >>> 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]
person Eduardo Soares    schedule 21.01.2019
comment
Привет, Эдуардо, спасибо за ваш ответ, но я явно ищу решение, которое использует graph-tool и которое можно использовать с весами края netagive. Кроме того, я хотел бы иметь возможность использовать структуру DAG. - person netword; 21.01.2019