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.Dijkstra.
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 goes into the queue.
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.Dijkstra uses a binary heap and costs O((V+E) log V). It goes on until every vertex it can reach is settled, and a vertex it can't reach keeps math.MaxFloat64 in the result.
path.DijkstraSimple returns the same distances with a plain list and a linear scan instead of a heap, in O(V²). The performance card on this page times both on each example graph.
New York streets
The main streets of Lower Manhattan and Downtown Brooklyn, from OpenStreetMap, with the Brooklyn and Manhattan Bridges between them. 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 24 to 40 km/h by road type where the map has no limit.
A directed, weighted graph with 295 vertices and 669 edges.
Map data © OpenStreetMap contributors.
How many minutes is the quickest drive from Canal St & Broadway in Manhattan to Court St & Joralemon St in Brooklyn?
The shortest distance from Canal St & Broadway to Court St & Joralemon St is 5.22. The run also finds the distance to the other 293 vertices Canal St & Broadway can reach.
Step by step
- Every distance starts at ∞, except Canal St & Broadway, which is 0. Put Canal St & Broadway in the queue.
- Take Canal St & Broadway from the queue. Its distance, 0, is now final.
- Canal St & Broadway to Broadway & Walker St: 0 + 0.19 = 0.19, so Broadway & Walker St's distance becomes 0.19.
- Canal St & Broadway to Canal St & Lafayette St: 0 + 0.29 = 0.29, so Canal St & Lafayette St's distance becomes 0.29.
- Canal St & Broadway to Canal St & W Broadway: 0 + 0.59 = 0.59, so Canal St & W Broadway's distance becomes 0.59.
- Take Broadway & Walker St from the queue. Its distance, 0.19, is now final.
653 more steps lead to the last one:
- Done. Every distance from Canal St & Broadway is final.
Use it in Go
dist := path.Dijkstra(g, "Canal St & Broadway")
fmt.Println(dist["Court St & Joralemon St"])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
- 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.