1
$\begingroup$

There are plenty material about bidirectional search with non-negative edge weights. One example is this paper. I am looking for any improvements using a bidirectional approach for acyclic digraphs with possibly negative weight edges.

The main approach for mono-directional search on possibly negative edge weights is Bellman-Ford. However, i don't think there's any valid early termination criteria that makes bidirectional Bellman-Ford better than the mono-directional.

Can someone provide ideas or references for a bidirectional search on an acyclic digraphs with possibly negative edge weights?

Thanks in advance.

$\endgroup$
  • $\begingroup$ Dear Victor, the paper you cite is not just an example of bidirectional search, it is THE paper :) ;) Actually, Ira asks in that manuscript whether it is possible to achieve the same improvements observed in brute-force search using heuristics or not. So far, no one has been able to do it (considering only positive edge weights!), needless to mention possibly negative edge weights. If you think this comment might constitute an answer let me know to develop it to a larger extent, but as far as I can tell there has not been any contribution in the line you mention. $\endgroup$ – Carlos Linares López May 4 '17 at 9:34
  • $\begingroup$ Hi Carlos, thank you for your comment. In this paper (sciencedirect.com/science/article/pii/S1572528606000417) there's an bidirectional approach for the resource constrained shortest path problem, that another paper i'm reading claims to have adapted for the common shortest path problem. If i understood correctly, this paper uses dynamic programming, and in a worst case generates all paths. I made the question in the hope for an alternative approach. I think i'll use this dynamic programming approach and see how it behave. You can elaborate an answer if you like. Thanks $\endgroup$ – Victor Hugo May 4 '17 at 11:49
  • $\begingroup$ Hi there Victor. I would actually say your understanding is perfect. Note the following however: heuristic bidirectional search is not guaranteed (in the current state-of-the-art) to expand less nodes or just to save running time when being compared to heuristic uni-directional search. The main problem is the termination condition, even if a solution is found, guaranteeing optimality is much harder. Watch out indeed the termination condition of Algorithm 3 in the paper you mention. However, in the case of brute-force search you are in the safe zone :) Hope this clarifies the whole issue $\endgroup$ – Carlos Linares López May 4 '17 at 12:04
  • $\begingroup$ Can you define "better"? Bidirectional search is a heuristic which means it might not improve the worst-case running time, though it is often useful in practice -- in particular it helps in a certain class of situations. Can you characterize your particular situation, to help identify heuristics that might be suitable for it? $\endgroup$ – D.W. May 6 '17 at 0:44
  • $\begingroup$ Hi @D.W, what situations does bidirectional search performs better? I don't know how to describe my situation for you. I'm solving a pricing problem, i have a dag with possible negative edges, when there's a column to be added. The graph is described in details in this paper: researchgate.net/publication/… $\endgroup$ – Victor Hugo May 8 '17 at 2:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.