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.

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

How it works

A* is how a navigation app finds one route from A to B. It runs like Dijkstra, but it orders its queue by the time so far plus a guess of the time left to B. So it always looks first at the vertex that seems to lead to B soonest, and it stops as soon as B leaves the queue. Dijkstra orders by the time so far alone and spreads out in every direction alike.

The guess on this page is the straight-line distance to B divided by the fastest speed on the map: the most distance per minute between its two ends that any street covers. No route can beat a straight line at that speed, so the guess never says more than the true time, and the route A* returns is the quickest. A guess that can say more than the true time can return a slower route. The guess needs each vertex's place, which only works where the vertices have positions, such as on a map.

This guess is also consistent: it never drops by more than the time of the street between two vertices. Then each vertex leaves the queue once, and A* costs O((V+E) log V), less in practice, since it stops at B. gograph calls the guess at most once for each vertex and never for B. With a guess that isn't consistent, it can take a vertex out of the queue again when a quicker way to it turns up.

path.AStar takes the edge cost and the guess as functions. A nil cost uses the edge weight, and a nil guess makes it Dijkstra. A negative cost returns ErrNegativeWeight, and a goal the start can't reach returns ErrUnreachable. Landmarks, the ALT method, give a sharper guess than a straight line on road networks.

San Francisco streets

The main streets of San Francisco from the Embarcadero to Van Ness Avenue and the Mission, from OpenStreetMap, with the freeways that cross SoMa. 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 22 to 40 km/h by road type where the map has no limit.

A directed, weighted graph with 248 vertices and 548 edges.

Map data © OpenStreetMap contributors.

What is the quickest drive from The Embarcadero & Mission St to 16th St & S Van Ness Ave in the Mission, and how much of the city does the search look at to find it?

The quickest drive from The Embarcadero & Mission St to 16th St & S Van Ness Ave takes 6.42 minutes, along 24 streets. path.DijkstraPaths finds the same time by settling all 248 vertices The Embarcadero & Mission St can reach.

Step by step

  1. Every time starts at ∞, except The Embarcadero & Mission St, which is 0. The guess of the time left is the straight-line distance to 16th St & S Van Ness Ave at 64 km/h, the fastest any street on the map goes between its two ends, so it never says more than the true time. From The Embarcadero & Mission St it is 3.6183 minutes, so The Embarcadero & Mission St goes in the queue at 0 + 3.6183 = 3.6183.
  2. Take The Embarcadero & Mission St from the queue: 0 minutes so far plus a guess of 3.6183 to go makes 3.6183, the lowest in the queue.
  3. The Embarcadero & Mission St to The Embarcadero & Howard St: 0 + 0.25 = 0.25. The guess from The Embarcadero & Howard St is 3.5755, so The Embarcadero & Howard St goes in the queue at 0.25 + 3.5755 = 3.8255.
  4. The Embarcadero & Mission St to The Embarcadero near Ferry Plaza (S): 0 + 0.11 = 0.11. The guess from The Embarcadero near Ferry Plaza (S) is 3.6472, so The Embarcadero near Ferry Plaza (S) goes in the queue at 0.11 + 3.6472 = 3.7572.
  5. Take The Embarcadero near Ferry Plaza (S) from the queue: 0.11 minutes so far plus a guess of 3.6472 to go makes 3.7572, the lowest in the queue.
  6. The Embarcadero near Ferry Plaza (S) to The Embarcadero near Ferry Plaza (N): 0.11 + 0.02 = 0.13. The guess from The Embarcadero near Ferry Plaza (N) is 3.6516, so The Embarcadero near Ferry Plaza (N) goes in the queue at 0.13 + 3.6516 = 3.7816.

272 more steps lead to the last one:

  1. Take 16th St & S Van Ness Ave from the queue at 6.42 minutes. That's the goal, so the quickest route there is known, and A* stops. It settled 114 vertices, where Dijkstra settles 190 by the time it reaches 16th St & S Van Ness Ave.

Use it in Go

goal := where["16th St & S Van Ness Ave"]
guess := func(v string) float64 {
	p := where[v]
	return math.Hypot(p[0]-goal[0], p[1]-goal[1]) / speed
}

route, minutes, err := path.AStar(g, "The Embarcadero & Mission St", "16th St & S Van Ness Ave", nil, guess)
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.
  • 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.
  • 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