Multi-source Dijkstra

Finds the nearest of several sources for every vertex, and the distance from it, in one search.

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

How it works

Multi-source Dijkstra answers which source is nearest to each vertex, such as which warehouse can reach each address soonest. It puts every source in the queue at distance 0 and then runs Dijkstra's algorithm once. Each vertex is settled by whichever source gets there first, so the areas around the sources grow together until they meet.

One search settles each vertex once, so it costs O((V+E) log V) however many sources there are. Running path.Dijkstra from each source instead settles every vertex once per source. The performance card on this page times both.

path.DijkstraMultiSource returns a NearestSources value with Source, Distance and PathTo for any vertex. When two sources are equally near, the one listed first wins, so the same sources give the same answer on every run. Distances run along the edges, from a source to the vertex. On a map with one-way streets, that is the drive from the warehouse to the address, and the drive back can differ.

Rasht streets

The main streets of Rasht in northern Iran, from OpenStreetMap, with the Gohar Roud and Zar Joub rivers running through the city. Each intersection is named after its streets in English, 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 298 vertices and 568 edges.

Map data © OpenStreetMap contributors.

With three warehouses across the city, which one should deliver to each intersection, and what is the longest drive any of them has?

Warehouse 1 at Moallem Blvd & Madar Sq serves 103, 2 at Shohada Blvd & Mahdieh St serves 92 and 3 at Roudbari St near Azimi St serves 103. The longest drive is 8.02, from warehouse 2 to Modarres Hwy near Navy Sq (S).

Step by step

Put every warehouse in the queue at 0: 1 at Moallem Blvd & Madar Sq, 2 at Shohada Blvd & Mahdieh St and 3 at Roudbari St near Azimi St. Each place goes to the warehouse that can reach it soonest, so one search serves them all.
Take Moallem Blvd & Madar Sq from the queue. It is warehouse 1, at 0 from itself.
Moallem Blvd & Madar Sq to Moallem Blvd & Pourrajab 17 St: 0 + 0.92 = 0.92, so Moallem Blvd & Pourrajab 17 St goes to warehouse 1 at 0.92.
Moallem Blvd & Madar Sq to Moallem Blvd near Madar Sq (E): 0 + 0.06 = 0.06, so Moallem Blvd near Madar Sq (E) goes to warehouse 1 at 0.06.
Moallem Blvd & Madar Sq to Moallem Blvd near Madar Sq (W): 0 + 0.06 = 0.06, so Moallem Blvd near Madar Sq (W) goes to warehouse 1 at 0.06.
Take Shohada Blvd & Mahdieh St from the queue. It is warehouse 2, at 0 from itself.

628 more steps lead to the last one:

Done. Every place has its nearest warehouse. One search settled 298 places. path.Dijkstra from each warehouse in turn would settle 894 between them.

Use it in Go

nearest, err := path.DijkstraMultiSource(g, "Moallem Blvd & Madar Sq", "Shohada Blvd & Mahdieh St", "Roudbari St near Azimi St")
if err != nil {
	return err
}
for _, v := range g.GetAllVertices() {
	from, ok := nearest.Source(v.Label())
	if !ok {
		continue
	}
	minutes, _ := nearest.Distance(v.Label())
	fmt.Println(v.Label(), from.Label(), minutes)
}

Example graphs

New York streets, 295 vertices and 669 edges
London streets, 274 vertices and 598 edges
San Francisco streets, 248 vertices and 548 edges
Rasht streets, 298 vertices and 568 edges
Delivery area, 8 vertices and 12 edges
Downtown grid, 20 vertices and 60 edges
One-way city, 45 vertices and 88 edges
Metro region, 100 vertices and 346 edges