COIN-OR::LEMON - Graph Library

Opened 9 years ago

Last modified 6 years ago

#249 assigned enhancement

Bidirectional Bfs and Dijkstra

Reported by: kpeter Owned by: kpeter
Priority: major Milestone:
Component: core Version: hg main
Keywords: Cc:
Revision id:

Description

It would be nice to have bidirectional Bfs and Dijkstra implementation in LEMON for the s-t shortest path problem.

Theoretically it is simple: the algorithm should be started "in parallel" from the source node s on the original graph and from the target node t on the reversed graph. As soon as we have a node u for which both direction have set the final dist and pred values, we can finish searching and construct the s->t path form the s->u path and the opposite of the t->u path. It could be faster by about a factor of two due to smaller search spaces.

However it is not clear for me how difficult it would be to implement it.

Change History (4)

comment:1 in reply to: ↑ description ; follow-up: Changed 9 years ago by alpar

Replying to kpeter:

It would be nice to have bidirectional Bfs and Dijkstra implementation in LEMON for the s-t shortest path problem.

Theoretically it is simple: the algorithm should be started "in parallel" from the source node s on the original graph and from the target node t on the reversed graph. As soon as we have a node u for which both direction have set the final dist and pred values, we can finish searching and construct the s->t path form the s->u path and the opposite of the t->u path.

It is a bit more difficult, even theoretically (it may be that the path s->u->t is not the shortest one).

comment:2 in reply to: ↑ 1 Changed 9 years ago by kpeter

Replying to alpar:

It is a bit more difficult, even theoretically (it may be that the path s->u->t is not the shortest one).

Oops, I'm sorry. You are right. I've heard (or studied?) this method in this way, but it's wrong.

E.g. G = ({s,u,v,w,t},{su,ut,sv,vw,wt}), c(su)=c(ut)=80, c(sv)=c(w,t)=10, c(vw)=100. Here the shortest path is <sv,vw,wt>, not <su,ut>.

comment:3 Changed 8 years ago by kpeter

  • Milestone LEMON 1.2 release deleted

comment:4 Changed 6 years ago by kpeter

  • Owner changed from alpar to kpeter
  • Status changed from new to assigned

Tamas Bibok implemented bidirectional Dijkstra and A* (A-star) algorithms for LEMON. These codes and his BSc thesis (in Hungarian) can be found in this repository:
http://lime.cs.elte.hu/~kpeter/hg/hgwebdir.cgi/lemon-astar/

Note: See TracTickets for help on using tickets.