Проверка веса отрицательного фронта в boost's dijkstra_shortest_paths

Question

Я использую библиотеку графов буста, чтобы позвонить на dijkstra_shortest_paths.Однако у меня есть кое-что особенное в том, что weight_map на самом деле является функтором.Следовательно, каждый раз, когда библиотека повышения требует веса ребра, мой функтор вызывается, выполняет сложные вычисления и возвращает результат для повышения.

К сожалению, в dijkstra_shortest_paths.hpp метод struct dijkstra_bfs_visitorexamine_edge имеет get вызов карты весов только для проверки, является ли возвращаемое значение отрицательным.Я полностью осознаю, что не могу использовать алгоритм Дейкстры с отрицательными значениями, и я уверен, что мой функтор возвращает только положительные значения.Однако эта проверка заставляет мой функтор вызываться дважды для каждого ребра.Поскольку он выполняет сложное вычисление, я бы хотел избежать его выполнения дважды (результаты не меняются между вызовами ... каждый ребро получает одинаковое ожидание во время dijkstra_shortest_paths прогона).

Пока что яЯ вручную проверяю ребро, переданное функтору, и в случае повторного вызова я возвращаю предыдущий запомненный результат.Очевидно, это скорее обходной путь, чем решение.

Я попытался пропустить своего собственного посетителя, который перезаписывает examine_edge, однако оригинальный метод, заданный параметром boost dijkstra_bfs_visitor, все еще применяется.

Кто-нибудь знает, есть ли лучший способ справиться с этой ситуацией и как-то избежать проверки веса отрицательного края?

Answer 1

Я предлагаю вам использовать ленивые вычисления, чтобы гарантировать, что каждое дорогостоящее вычисление выполняется не более одного раза.Самый простой способ реализовать это - дать вашему Edge классу getWeight() ленивый метод получения, я не знаком с библиотекой, которую вы используете, поэтому я не уверен, как вы интегрируете это с функтором.

Answer 2

Вы правы, даже если у вас есть собственный посетитель, тест отрицательности будет выполнен.

  void examine_edge(Edge e, Graph& g) {
    if (m_compare(get(m_weight, e), m_zero))
        boost::throw_exception(negative_edge());
    m_vis.examine_edge(e, g);
  } 

Но в любом случае весовая карта должна вызываться несколько раз (см. Boost doc ):

 for each vertex v in Adj[u]
  if (w(u,v) + d[u] < d[v])
    d[v] := w(u,v) + d[u]

Просто вызовите djikstra с предварительно вычисленной картой весов, каждый вес ребра должен быть вычислен в любом случае.