Graphs

Shortest Path (Unweighted, via BFS)

BFS explores a graph layer by layer, so the first time it reaches a vertex is along a shortest path. Track dist[v] and parent[v] while exploring, then walk parents back from the target to reconstruct the route.

Algorithm

On the canonical graph from graph-adjacency-list, the shortest path from 1 to 6 is [1 2 4 5 6] (space-separated) with distance 4. The path is rebuilt from parent: 6 -> 5 -> 4 -> 2 -> 1, reversed.

layers equal distance BFS order equals distance in an unweighted graph.

Basic Implementation

basic.go
Replay: real traced execution (multi-file project)
package main

import "fmt"

func main() {
	adj := map[int][]int{
		1: {2, 3},
		2: {1, 4},
		3: {1, 4},
		4: {2, 3, 5},
		5: {4, 6},
		6: {5},
	}
	src := 1
	dst := 6
	dist := map[int]int{src: 0}
	parent := map[int]int{src: 0}
	queue := []int{src}
	for len(queue) > 0 {
		v := queue[0]
		queue = queue[1:]
		for _, nb := range adj[v] {
			if _, ok := dist[nb]; !ok {
				dist[nb] = dist[v] + 1
				parent[nb] = v
				queue = append(queue, nb)
			}
		}
	}
	path := []int{}
	for node := dst; node != 0; node = parent[node] {
		path = append(path, node)
	}
	for i, j := 0, len(path)-1; i < j; i, j = i+1, j-1 {
		path[i], path[j] = path[j], path[i]
	}
	fmt.Println(path)
	fmt.Println(dist[dst])
}

  1. dist ← {1: 0}

    15dst := 616dist := map[int]int{src: 0}17parent := map[int]int{src: 0}
    values this step{1: 0}dist

  2. parent ← {1: null}

    16dist := map[int]int{src: 0}17parent := map[int]int{src: 0}18queue := []int{src}
    values this step{1: null}parent

  3. dist ← {1: 0, 2: 1, 3: 1}, parent ← {1: null, 2: 1, 3: 1}, queue ← [2, 3]

    19for len(queue) > 0 {20	v := queue[0]21	queue = queue[1:]
    values this step{1: 0, 2: 1, 3: 1}dist{1: null, 2: 1, 3: 1}parent[2, 3]queue1dequeue

  4. dist ← {1: 0, 2: 1, 3: 1, 4: 2}, parent ← {1: null, 2: 1, 3: 1, 4: 2}

    19for len(queue) > 0 {20	v := queue[0]21	queue = queue[1:]
    values this step{1: 0, 2: 1, 3: 1, 4: 2}dist{1: null, 2: 1, 3: 1, 4: 2}parent[3, 4]queue2dequeue

  5. dist ← {1: 0, 2: 1, 3: 1, 4: 2}, parent ← {1: null, 2: 1, 3: 1, 4: 2}

    19for len(queue) > 0 {20	v := queue[0]21	queue = queue[1:]
    values this step{1: 0, 2: 1, 3: 1, 4: 2}dist{1: null, 2: 1, 3: 1, 4: 2}parent[4]queue3dequeue

  6. dist ← {1: 0, 2: 1, 3: 1, 4: 2, 5: 3}, parent ← {1: null, 2: 1, 3: 1, 4: 2, 5: 4}

    19for len(queue) > 0 {20	v := queue[0]21	queue = queue[1:]
    values this step{1: 0, 2: 1, 3: 1, 4: 2, 5: 3}dist{1: null, 2: 1, 3: 1, 4: 2, 5: 4}parent[5]queue4dequeue

  7. dist ← {1: 0, 2: 1, 3: 1, 4: 2, 5: 3, 6: 4}, parent ← {1: null, 2: 1, 3: 1, 4: 2, 5: 4, 6: 5}

    19for len(queue) > 0 {20	v := queue[0]21	queue = queue[1:]
    values this step{1: 0, 2: 1, 3: 1, 4: 2, 5: 3, 6: 4}dist{1: null, 2: 1, 3: 1, 4: 2, 5: 4, 6: 5}parent[6]queue5dequeue

  8. dist ← {1: 0, 2: 1, 3: 1, 4: 2, 5: 3, 6: 4}, parent ← {1: null, 2: 1, 3: 1, 4: 2, 5: 4, 6: 5}

    19for len(queue) > 0 {20	v := queue[0]21	queue = queue[1:]
    values this step{1: 0, 2: 1, 3: 1, 4: 2, 5: 3, 6: 4}dist{1: null, 2: 1, 3: 1, 4: 2, 5: 4, 6: 5}parent[]queue6dequeue

  9. path ← [1, 2, 4, 5, 6]

    30path := []int{}31for node := dst; node != 0; node = parent[node] {32	path = append(path, node)
    values this step[1, 2, 4, 5, 6]path{1: null, 2: 1, 3: 1, 4: 2, 5: 4, 6: 5}parent

  10. stdout ← [1 2 4 5 6]

    36}37fmt.Println(path)38fmt.Println(dist[dst])
    values this step[1 2 4 5 6]stdout[1, 2, 4, 5, 6]path

  11. stdout ← 4

    37	fmt.Println(path)38	fmt.Println(dist[dst])39}
    values this step4stdout4dist[6]

  12. BFS path ← 1 -> 2 (1 edge, cost 10), cheaper weighted path ← 1 -> 3 -> 2 (2 edges, cost 2)

    37	fmt.Println(path)38	fmt.Println(dist[dst])39}
    values this step1 -> 2 (1 edge, cost 10)BFS path1 -> 3 -> 2 (2 edges, cost 2)cheaper weighted pathuse Dijkstra with a priority queueweighted algorithm1->2 weight 10, 1->3 weight 1, 3->2 weight 1edge weights

Complexity

  • Time: O(V + E)
  • Space: O(V)

Implementation notes

  • Go: a dist map doubles as the visited check, parent records predecessors (0 marks the source), and a slice index walks the queue.
  • The replay shows dist, parent, and the queue filling in, then the reconstructed path. It also contrasts that unweighted result with a weighted graph where Dijkstra with a priority queue is required.