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.
School run
Six places on the morning drive to school. Most streets go both ways, and each edge is the travel time in minutes.
A directed, weighted graph with 6 vertices and 13 edges.
How many minutes is the quickest drive from home to each place, including the school?
Use it in Go
dist := path.Dijkstra(g, "Home")
fmt.Println(dist["School"])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.