Bidirectional search

Finds the quickest route from one vertex to another by searching forward from the start and backward from the goal at once, until the two searches meet.

Time complexity O((V+E) log V), gograph function path.Bidirectional.

How it works

Bidirectional search runs two Dijkstra searches at once: one forward from the start and one backward from the goal. Each step takes the vertex with the smaller time from the two queues, so the two sides grow at the same pace. Each side covers about half the distance, so on a road map it looks at a fraction of what one search would. Routing engines use it on its own and under faster methods such as contraction hierarchies.

The search from the goal follows edges in reverse: on a directed graph it walks the edges that lead into a vertex, so a one-way street that leads into the goal is taken backward from the goal. Each time one side reaches a vertex the other side has reached, the two times add up to a route, and the search keeps the quickest one it has found.

It can't stop the moment the two sides first touch, since a quicker route can pass through vertices neither side has settled. It stops once the two smallest times left in the queues add up to no less than the best route: any route not found yet goes through a vertex still in a queue and takes at least that long.

path.Bidirectional takes the edge cost as a function, and a nil cost uses the edge weight. A negative cost returns ErrNegativeWeight, and a goal the start can't reach returns ErrUnreachable. Ties break by the order vertices and edges were added, so the same graph gives the same route on every run.

London streets

The main roads of central London from Westminster to the City, from OpenStreetMap, with the bridges over the Thames to Southwark and Waterloo. Each intersection is named after its streets, one-way streets go one way, and each edge is the minutes to drive it at the speed limit, or at 20 to 32 km/h by road type where the map has no limit.

A directed, weighted graph with 274 vertices and 598 edges.

Map data © OpenStreetMap contributors.

What is the quickest drive from Trafalgar Sq & Strand to Tower Bridge Rd & Tooley St across the Thames, searching from both ends at once?

The quickest drive from Trafalgar Sq & Strand to Tower Bridge Rd & Tooley St takes 8.37 minutes, along 16 streets.

Step by step

  1. Search forward from Trafalgar Sq & Strand and backward from Tower Bridge Rd & Tooley St at once. Each side has its own queue, ordered by time from its end, and each round settles the vertex with the smaller time of the two.
  2. The next times are 0 from the start and 0 from the goal: 0 + 0 = 0, and no route is known yet, so go on. Settle Trafalgar Sq & Strand from the start at 0.
  3. Trafalgar Sq & Strand to St Martin's Pl & Charing Cross Rd: 0 + 0.37 = 0.37.
  4. Trafalgar Sq & Strand to Trafalgar Sq & Charing Cross: 0 + 0.12 = 0.12.
  5. The next times are 0.12 from the start and 0 from the goal: 0.12 + 0 = 0.12, and no route is known yet, so go on. Settle Tower Bridge Rd & Tooley St from the goal at 0.
  6. Tooley St & Queen Elizabeth St to Tower Bridge Rd & Tooley St leads into Tower Bridge Rd & Tooley St, so the search from the goal takes it backward, from Tower Bridge Rd & Tooley St to Tooley St & Queen Elizabeth St. It follows every street in reverse, so a one-way street counts only the way it leads to the goal. 0 + 0.14 = 0.14.

449 more steps lead to the last one:

  1. Stop: the next times, 4.17 from the start and 4.2 from the goal, add up to 8.37, no less than the best route, 8.37, so no route left to find can be quicker. The quickest route meets at Blackfriars Rd & Blackfriars Bridge and takes 8.37 minutes. The searches settled 105 vertices from the start and 90 from the goal.

Use it in Go

route, minutes, err := path.Bidirectional(g, "Trafalgar Sq & Strand", "Tower Bridge Rd & Tooley St", nil)
if err != nil {
	return err // path.ErrUnreachable when the goal is out of reach
}
fmt.Println(minutes)
for _, v := range route {
	fmt.Println(v.Label())
}

Example graphs

More in Shortest paths

  • Dijkstra: Finds the shortest distance from a start vertex to every other vertex when no edge weight is negative.
  • A*: Finds the quickest route from one vertex to another, looking first where a guess of the time left says the goal is, so it settles far fewer vertices than Dijkstra.
  • k shortest paths: Finds the k quickest routes from one vertex to another that don't repeat a vertex, quickest first, the way a navigation app offers a few routes.
  • Beam search: Looks for a route from one vertex to another while keeping only the few best partial paths at each step, so its memory and time stay bounded, at the cost of sometimes missing the best route.
  • Multi-source Dijkstra: Finds the nearest of several sources for every vertex, and the distance from it, in one search.
  • k-center: Chooses k centers so that the vertex farthest from its nearest center is as near as it can make it.
  • Bellman-Ford: Finds the shortest distance from a start vertex to every other vertex, even with negative weights, and reports a negative cycle when the start can reach one.
  • Floyd-Warshall: Finds the shortest distance between every pair of vertices, even with negative weights, by letting paths stop at one more vertex in each round.

All algorithms