Implementing Bidirectional A* Shortest Path Algorithm

I am implementing a symmetric bidirectional A* shortest path algorithm, as mentioned in [Goldberg and Harrelson,2005]. This is only for understanding the algorithm, therefore I used the most basic version without any optimization steps.

My problem is the bidirectional algorithm appears to scan almost two times the number of edges scanned in a uni-directional A* search on the test graph.

Example: a s-t query on a road network using A* (left) and bidirectional A* (right). Nodes scanned by the forward and backward search are colored in red and green, respectively. The heuristic function is simply the euclidean distance to t or s. The computed paths (blue) are correct in both figures.

I may be understanding the algorithm logic incorrectly. Here is how I adapted unidirectional A* to bidirectional (from reference)

• Alternate between forward search and backward search. Maintain variable mu as the current best estimate of s-t path length.
• In the forward search, if w in edge (v,w) has been scanned by the backward search, do not update w's labels.
• Each time a forward search scan (v,w) and if w has been scanned by the reverse search, update mu if dist(s,v) + len(v,w)+dist(w,t)<= mu
• Stopping condition: when forward search is about to scan a vertex v with dist(s,v) + potential_backward(v) >= mu
• (Similar rules apply in the backward search)

I'd appreciate if anyone can point out the flaws in my implementation, or some more detailed explanation of the bidirectional A* algorithm.

Code in Python:

""" bidirectional_a_star: bidirectional A* search g: input graph (networkx object) s, t: source and destination nodes pi_forward, pi_backward: forward and backward potential function values wt_attr: attribute name to be used as edge weight """ def bidirectional_a_star(g,s,t,pi_forward, pi_backward, wt_attr='weight' ): # initialization gRev = g.reverse() # reverse graph ds = { v:float('inf') for v in g } # best distances from s or t dt = ds.copy() ds[s]=0 dt[t]=0 parents = {} # predecessors in forward/backward search parentt = {} pqueues =[(ds[s]+pi_forward[s],s)] # priority queues for forward/backward search pqueuet = [(dt[t]+pi_backward[t],t)] mu = float('inf') # best s-t distance scanned_forward=set() # set of scanned vertices in forward/backward search scanned_backward=set() while (len(pqueues)>0 and len(pqueuet)>0): # forward search (priority_s,vs) = heappop(pqueues) # vs: first node in forward queue if (priority_s >= mu): # stop condition break for w in g.neighbors(vs): # scan outgoing edges from vs newDist = ds[vs] + g.edge[vs][w][wt_attr] if (ds[w] > newDist and w not in scanned_backward): ds[w] = newDist # update w's label parents[w] = vs heappush(pqueues, (ds[w]+pi_forward[w] , w) ) if ( (w in scanned_backward) and (newDist + dt[w]<mu)): mu = newDist+dt[w] scanned_forward.add(vs) # mark vs as "scanned" # backward search (priority_t,vt) = heappop(pqueuet) # vt: first node in backward queue if (priority_t>= mu ): break for w in gRev.neighbors(vt): newDist = dt[vt] + gRev.edge[vt][w][wt_attr] if (dt[w] >= newDist and w not in scanned_forward): if (dt[w] ==newDist and parentt[vt] < w): continue else: dt[w] = newDist parentt[w] = vt heappush(pqueuet,(dt[w]+pi_backward[w],w)) if ( w in scanned_forward and newDist + ds[w]<= mu): mu = newDist+dt[w] scanned_backward.add(vt) # compute s-t distance and shortest path scanned = scanned_s.intersection(scanned_t) minPathLen = min( [ ds[v]+dt[v] for v in scanned ] ) # find s-t distance minPath = reconstructPath(ds,dt,parents,parentt,scanned) # join s-v and v-t path return (minPathLen, minPath) 

Update

Following Janne's comment, I created a demo that tests the search on a few examples. The implementation has been improved, and fewer nodes are scanned.

Example: Shortest path from the red dot to the green dot on a (directed) grid graph. The middle figure highlights nodes scanned by A*; The right figure shows nodes scanned by the forward search (orange) and those scanned by the backward search (blue)

However, on the road network, the union of nodes scanned by the forward search and those scanned by the backward search is still more than the number of nodes scanned by a unidirectional search. Perhaps this depends on the input graph?

1 Answer

Hy, Your problem is that, you don't put the right condition to stop, the stop condition is when (forward and backward search are meet),