Dijkstra's algorithm finds the shortest route from one starting point to every other, by always going to the nearest place it has not settled yet.
Strategy
Greedy
Always settle the nearest place you have not visited yet. Once it is settled, its distance is final.
- Choose: take the unsettled node with the smallest known distance.
- Relax: offer each of its neighbors a shorter way in through it.
- Repeat: settle the next nearest until every reachable node is done.
Settle one city at a time. Green edges are the routes that won.
Purpose
Find the shortest route from one starting point to everywhere else.
Input
A graph whose roads carry lengths, and the node to start from.
Output
The distance to every node, plus the previous-node map you walk backwards to get a route.
Constraints
- Every road length has to be positive. A negative one breaks the reason the nearest-first choice is safe.
- A node with no route from the start keeps its starting distance, so check for that before using it.
- Lengths are whole numbers here, and the same code works for floats.
How Dijkstra's algorithm works
Picture driving out from home, always to the nearest place you have not been yet. The moment you arrive you know the shortest way there, because any other route would have gone somewhere further away first. Road lengths have to be positive.
What Dijkstra's algorithm keeps track of
| Name | Type | What it is for |
|---|---|---|
| road | struct{ to string; miles int } | One way out of a city, and how far it goes. |
| Graph | map[string][]road | Every city, and the roads leading out of it. |
| dist | map[string]int | The shortest distance found to each city so far. |
| prev | map[string]string | The city you arrived from, which rebuilds the route at the end. |
| done | map[string]bool | Cities whose distance is final, so they are never reworked. |
| queue | container/heap | Hands back the nearest city still waiting. |
Walk through it
1 Give every road a length
Each city keeps the roads leaving it. Adding at both ends makes the road two-way.
type road struct {
to string
miles int
}
type Graph map[string][]road
func (g Graph) AddRoad(a, b string, miles int) {
g[a] = append(g[a], road{b, miles})
g[b] = append(g[b], road{a, miles})
}2 Start at zero and leave the rest unknown
A city missing from dist has no known route yet, so the first one found always wins.
dist := map[string]int{start: 0}
prev := map[string]string{}
done := map[string]bool{}
q := &queue{{start, 0}}
heap.Init(q)3 Always take the nearest city still waiting
The heap hands back the smallest distance. A city can sit in the queue twice, so skip it once settled.
for q.Len() > 0 {
cur := heap.Pop(q).(item)
if done[cur.city] {
continue
}
done[cur.city] = true4 Offer every neighbor a shorter way in
Add the road to the distance you already have. When that beats the neighbor's best, record it and queue the neighbor.
for _, r := range g[cur.city] {
next := cur.miles + r.miles
if best, seen := dist[r.to]; !seen || next < best {
dist[r.to] = next
prev[r.to] = cur.city
heap.Push(q, item{r.to, next})
}
}
}5 Walk the trail backwards to get the route
prev holds the city you arrived from, so follow it back from the destination and reverse.
route := []string{dest}
for at := dest; at != start; {
up, ok := prev[at]
if !ok {
return nil
}
at = up
route = append([]string{at}, route...)
}The whole program
Five roads between five cities, then the drive to three of them.
package main
import (
"container/heap"
"fmt"
)
// road is one way out of a city, and how far it goes.
type road struct {
to string
miles int
}
type Graph map[string][]road
// AddRoad records the road at both ends, so it can be driven either way.
func (g Graph) AddRoad(a, b string, miles int) {
g[a] = append(g[a], road{b, miles})
g[b] = append(g[b], road{a, miles})
}
// item is a city waiting to be visited, ordered by the shortest distance
// found to it so far.
type item struct {
city string
miles int
}
type queue []item
func (q queue) Len() int { return len(q) }
func (q queue) Less(i, j int) bool { return q[i].miles < q[j].miles }
func (q queue) Swap(i, j int) { q[i], q[j] = q[j], q[i] }
func (q *queue) Push(x any) { *q = append(*q, x.(item)) }
func (q *queue) Pop() any {
old := *q
last := old[len(old)-1]
*q = old[:len(old)-1]
return last
}
// ShortestFrom returns the distance to every city reachable from start, and
// the city each one was reached from.
func ShortestFrom(g Graph, start string) (map[string]int, map[string]string) {
dist := map[string]int{start: 0}
prev := map[string]string{}
done := map[string]bool{}
q := &queue{{start, 0}}
heap.Init(q)
for q.Len() > 0 {
cur := heap.Pop(q).(item)
if done[cur.city] {
continue
}
done[cur.city] = true
for _, r := range g[cur.city] {
next := cur.miles + r.miles
if best, seen := dist[r.to]; !seen || next < best {
dist[r.to] = next
prev[r.to] = cur.city
heap.Push(q, item{r.to, next})
}
}
}
return dist, prev
}
// Route walks the prev map backwards from dest to rebuild the drive.
func Route(prev map[string]string, start, dest string) []string {
route := []string{dest}
for at := dest; at != start; {
up, ok := prev[at]
if !ok {
return nil
}
at = up
route = append([]string{at}, route...)
}
return route
}
func main() {
g := Graph{}
g.AddRoad("Providence", "Boston", 50)
g.AddRoad("Boston", "Hartford", 100)
g.AddRoad("Hartford", "New Haven", 40)
g.AddRoad("New Haven", "New York", 75)
g.AddRoad("Providence", "New Haven", 100)
dist, prev := ShortestFrom(g, "Providence")
fmt.Println(dist["New York"], Route(prev, "Providence", "New York"))
fmt.Println(dist["Hartford"], Route(prev, "Providence", "Hartford"))
fmt.Println(dist["Boston"], Route(prev, "Providence", "Boston"))
}$ go run main.go
175 [Providence New Haven New York]
140 [Providence New Haven Hartford]
50 [Providence Boston]Hartford comes out at 140 through New Haven, beating the 150 through Boston.