Shortest Paths (Dijkstra’s Algorithm)

Updated

October 31, 2026

Shortest Paths (Dijkstra’s Algorithm)

While Breadth-First Search finds the path with the fewest hops, real systems have weighted costs: network latencies, courier miles, fuel consumption, or processing fees. Dijkstra’s algorithm computes the single-source shortest path across a weighted graph with non-negative edge weights in \(O((V + E) \log V)\) time using a min-priority queue.

Graph Traversal and Dijkstra Relaxation

Mental model

Dijkstra maintains two maps: 1. dist[v]: The shortest known distance from the starting source to vertex \(v\) (initialized to \(\infty\), with dist[start] = 0). 2. prev[v]: The predecessor vertex on the optimal path.

At each step, the algorithm extracts the unvisited vertex \(u\) with the smallest known distance from a min-priority queue and relaxes all outgoing edges \((u, v, \text{weight})\):

\[\text{If } \text{dist}[u] + \text{weight} < \text{dist}[v] \implies \text{dist}[v] = \text{dist}[u] + \text{weight}\]

Relaxation Step:
(Depot) --[Known: 2]--> (Hub A) --[Weight: 3]--> (Dest)
                           \                        ^
                            \--[Weight: 1]-->(Hub B)-[Weight: 1]-/

Direct path: Depot -> Hub A -> Dest = 2 + 3 = 5
Relaxed path: Depot -> Hub A -> Hub B -> Dest = 2 + 1 + 1 = 4 (Optimal!)

Because edge weights are non-negative, the moment a vertex is popped from the min-priority queue, its calculated distance is permanently optimal.

Worked examples

Case 1: Complete Dijkstra implementation with path reconstruction

Save as dijkstra_delivery.go. Calculate the lowest-cost delivery route between warehouse dispatch points.

// dijkstra_delivery.go
package main

import (
    "container/heap"
    "fmt"
    "math"
)

type Edge struct {
    To     string
    Weight int
}

type WeightedGraph struct {
    adj map[string][]Edge
}

func NewWeightedGraph() *WeightedGraph {
    return &WeightedGraph{adj: make(map[string][]Edge)}
}

func (g *WeightedGraph) AddEdge(from, to string, weight int) {
    g.adj[from] = append(g.adj[from], Edge{To: to, Weight: weight})
    g.adj[to] = append(g.adj[to], Edge{To: from, Weight: weight}) // Undirected
}

// Priority Queue item
type Item struct {
    Node string
    Dist int
}

type PriorityQueue []Item

func (pq PriorityQueue) Len() int           { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool { return pq[i].Dist < pq[j].Dist } // Min-heap
func (pq PriorityQueue) Swap(i, j int)      { pq[i], pq[j] = pq[j], pq[i] }
func (pq *PriorityQueue) Push(x any)        { *pq = append(*pq, x.(Item)) }
func (pq *PriorityQueue) Pop() any {
    old := *pq
    n := len(old)
    x := old[n-1]
    *pq = old[0 : n-1]
    return x
}

type ShortestPathResult struct {
    Distance int
    Path     []string
}

func (g *WeightedGraph) Dijkstra(start, dest string) (ShortestPathResult, bool) {
    dist := make(map[string]int)
    prev := make(map[string]string)

    for node := range g.adj {
        dist[node] = math.MaxInt
    }
    dist[start] = 0

    pq := &PriorityQueue{}
    heap.Init(pq)
    heap.Push(pq, Item{Node: start, Dist: 0})

    for pq.Len() > 0 {
        top := heap.Pop(pq).(Item)
        u := top.Node
        currDist := top.Dist

        // Stale item check: if we found a shorter route to u already, skip
        if currDist > dist[u] {
            continue
        }

        if u == dest {
            break // Reached destination with optimal distance
        }

        for _, edge := range g.adj[u] {
            v := edge.To
            newDist := currDist + edge.Weight
            if newDist < dist[v] {
                dist[v] = newDist
                prev[v] = u
                heap.Push(pq, Item{Node: v, Dist: newDist})
            }
        }
    }

    if dist[dest] == math.MaxInt {
        return ShortestPathResult{}, false // Unreachable
    }

    // Reconstruct path
    var path []string
    curr := dest
    for curr != "" {
        path = append(path, curr)
        curr = prev[curr]
    }

    // Reverse path
    for i, j := 0, len(path)-1; i < j; i, j = i+1, j-1 {
        path[i], path[j] = path[j], path[i]
    }

    return ShortestPathResult{Distance: dist[dest], Path: path}, true
}

func main() {
    g := NewWeightedGraph()
    g.AddEdge("Main-Depot", "North-Hub", 4)
    g.AddEdge("Main-Depot", "South-Hub", 2)
    g.AddEdge("South-Hub", "North-Hub", 1)
    g.AddEdge("North-Hub", "Airport-Station", 7)
    g.AddEdge("South-Hub", "Midtown-Annex", 8)
    g.AddEdge("North-Hub", "Midtown-Annex", 3)
    g.AddEdge("Midtown-Annex", "Airport-Station", 1)

    res, found := g.Dijkstra("Main-Depot", "Airport-Station")
    if !found {
        fmt.Println("No route found")
        return
    }

    fmt.Printf("Lowest Delivery Latency: %d ms\n", res.Distance)
    fmt.Print("Optimal Route: ")
    for i, step := range res.Path {
        if i > 0 {
            fmt.Print(" -> ")
        }
        fmt.Print(step)
    }
    fmt.Println()
}

Run:

go run dijkstra_delivery.go

Output:

Lowest Delivery Latency: 7 ms
Optimal Route: Main-Depot -> South-Hub -> North-Hub -> Midtown-Annex -> Airport-Station

Notice that although Main-Depot -> North-Hub -> Airport-Station has fewer hops (2 hops, cost \(4+7 = 11\)), Dijkstra discovers the 4-hop route via South-Hub and Midtown-Annex with total cost \(2 + 1 + 3 + 1 = 7\)!

The trap

There are two primary traps when implementing Dijkstra’s algorithm:

  1. Negative Edge Weights: Dijkstra assumes that adding an edge can never decrease the total path cost. If a graph has negative edge weights, Dijkstra produces wrong answers or loops indefinitely. Graphs with negative weights require the Bellman-Ford algorithm.
  2. Stale Priority Queue Entries: In standard Go implementations, updating a node’s distance is achieved by pushing a new Item{Node: v, Dist: newDist} into the heap. Without the check if currDist > dist[u] { continue }, the algorithm wastes time re-exploring superseded paths, degrading performance.

The boring rule

  1. Use BFS for unweighted shortest path queries. Use Dijkstra when edges represent costs, times, distances, or latency.
  2. Always guard the main loop with if currDist > dist[u] { continue } to drop stale heap items instantly.
  3. Validate that all edge weights are \(\ge 0\).
  4. Stop the algorithm early when the target node is popped from the priority queue; its distance is provably finalized.

Try this

  1. Modify Dijkstra to return all reachable destinations and their shortest paths from start in a single run.
  2. Add a MaxStops parameter to restrict the search to routes with at most 3 intermediary transfers.