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.
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?
Use it in Go
dist := path.Dijkstra(g, "Gomnam Underpass & Gomnam Sq")
fmt.Println(dist["Zar Joub Sq & Shariati Blvd"])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.