Dijkstra
Finds the shortest distance from a start vertex to every other vertex when no edge weight is negative.
Time complexity O((V+E) log V), gograph function path.DijkstraPaths.
path.Dijkstra returns the same distances as a map, without the routes.
How it works
Dijkstra's algorithm gives the start a distance of 0 and every other vertex a distance of infinity, and keeps the vertices in a priority queue by distance. It takes the closest vertex out, which makes its distance final, and checks each edge from it. When the path through that vertex is shorter than a neighbor's current distance, the neighbor takes the shorter distance, and the edge it came by becomes its way in.
This works because no edge weight is negative. Once a vertex is the closest one left, no later path can reach it for less. With a negative edge that stops being true, and Bellman-Ford is the one to use. path.DijkstraPaths keeps one entry per vertex in a binary heap and moves it up when a shorter path turns up, so it costs O((V+E) log V). It goes on until every vertex it can reach is settled.
Distance and PathTo on its result give each distance and the route there, start first, and report false for a vertex the start can't reach, so there's no infinity to compare with. Of two routes that are equally short, it keeps the one it found first, and vertices at the same distance leave the queue in the order of the edges that reached them, so the same graph gives the same routes on every run.
path.Dijkstra returns the distances alone, with math.MaxFloat64 for a vertex it can't reach, and path.DijkstraSimple returns them with a plain list and a linear scan instead of a heap, in O(V²). The performance card on this page times all three on each example graph.
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.
How many minutes is the quickest drive from Gomnam Underpass & Gomnam Sq in the west of the city to Zar Joub Sq & Shariati Blvd, across both rivers?
The shortest distance from Gomnam Underpass & Gomnam Sq to Zar Joub Sq & Shariati Blvd is 8.81. The run also finds the distance to the other 296 vertices Gomnam Underpass & Gomnam Sq can reach.
Step by step
- Every distance starts at ∞, except Gomnam Underpass & Gomnam Sq, which is 0. Put Gomnam Underpass & Gomnam Sq in the queue.
- Take Gomnam Underpass & Gomnam Sq from the queue. Its distance, 0, is now final.
- Gomnam Underpass & Gomnam Sq to Beheshti Blvd & Gomnam Underpass: 0 + 0.33 = 0.33, so Beheshti Blvd & Gomnam Underpass's distance becomes 0.33. Put Beheshti Blvd & Gomnam Underpass in the queue.
- Gomnam Underpass & Gomnam Sq to Beheshti Frontage Rd near Gomnam Underpass: 0 + 0.13 = 0.13, so Beheshti Frontage Rd near Gomnam Underpass's distance becomes 0.13. Put Beheshti Frontage Rd near Gomnam Underpass in the queue.
- Gomnam Underpass & Gomnam Sq to Gomnam Blvd & Gomnam Frontage Rd: 0 + 0.27 = 0.27, so Gomnam Blvd & Gomnam Frontage Rd's distance becomes 0.27. Put Gomnam Blvd & Gomnam Frontage Rd in the queue.
- Gomnam Underpass & Gomnam Sq to Gomnam Bridge & Eftekhari Frontage Rd: 0 + 0.15 = 0.15, so Gomnam Bridge & Eftekhari Frontage Rd's distance becomes 0.15. Put Gomnam Bridge & Eftekhari Frontage Rd in the queue.
635 more steps lead to the last one:
- Done. Every distance from Gomnam Underpass & Gomnam Sq is final.
Use it in Go
paths, err := path.DijkstraPaths(g, "Gomnam Underpass & Gomnam Sq")
if err != nil {
return err
}
minutes, ok := paths.Distance("Zar Joub Sq & Shariati Blvd")
if !ok {
return nil // out of reach
}
route, _ := paths.PathTo("Zar Joub Sq & Shariati Blvd")
fmt.Println(minutes)
for _, v := range route {
fmt.Println(v.Label())
}
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
- School run, 6 vertices and 13 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
More in Shortest paths
- 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.
- 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.