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.
Downtown grid
Twenty intersections on a downtown street grid. Streets go both ways, Market is closed to cars between 2nd and 3rd, and each edge is the travel time in minutes.
A directed, weighted graph with 20 vertices and 60 edges.
How many minutes is the quickest drive from Pine & 1st to each intersection, with Market closed between 2nd and 3rd?
Use it in Go
dist := path.Dijkstra(g, "Pine & 1st")
fmt.Println(dist["River & 5th"])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.