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.

Delivery area

Eight stops in a small town. Streets are one way, and each edge is the travel time in minutes.

A directed, weighted graph with 8 vertices and 12 edges.

How many minutes is the quickest drive from the depot to each stop?

Use it in Go

dist := path.Dijkstra(g, "Depot")
fmt.Println(dist["Station"])

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.

All algorithms