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 distance and predecessor while exploring, then walk predecessors 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] with distance 4. The path is rebuilt from the predecessor of each vertex: 6 -> 5 -> 4 -> 2 -> 1, reversed.

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

Basic Implementation

basic.R
Replay: real traced execution (multi-file project)
adj <- list("1" = c(2, 3), "2" = c(1, 4), "3" = c(1, 4), "4" = c(2, 3, 5), "5" = c(4, 6), "6" = c(5))
src <- 1
dst <- 6
dist <- list()
parent <- list()
dist[[as.character(src)]] <- 0
parent[[as.character(src)]] <- 0
queue <- c(src)
head <- 1
while (head <= length(queue)) {
	v <- queue[head]
	head <- head + 1
	for (nb in adj[[as.character(v)]]) {
		if (is.null(dist[[as.character(nb)]])) {
			dist[[as.character(nb)]] <- dist[[as.character(v)]] + 1
			parent[[as.character(nb)]] <- v
			queue[length(queue) + 1] <- nb
		}
	}
}
path <- integer(0)
node <- dst
while (node != 0) {
	path[length(path) + 1] <- node
	node <- parent[[as.character(node)]]
}
path <- rev(path)
cat("[", paste(path, collapse = ", "), "]\n", sep = "")
cat(dist[[as.character(dst)]], "\n", sep = "")

  1. dist ← {1: 0}

    5parent <- list()6dist[[as.character(src)]] <- 07parent[[as.character(src)]] <- 0
    values this step{1: 0}dist

  2. parent ← {1: null}

    6dist[[as.character(src)]] <- 07parent[[as.character(src)]] <- 08queue <- c(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]

    10while (head <= length(queue)) {11	v <- queue[head]12	head <- head + 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}

    10while (head <= length(queue)) {11	v <- queue[head]12	head <- head + 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}

    10while (head <= length(queue)) {11	v <- queue[head]12	head <- head + 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}

    10while (head <= length(queue)) {11	v <- queue[head]12	head <- head + 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}

    10while (head <= length(queue)) {11	v <- queue[head]12	head <- head + 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}

    10while (head <= length(queue)) {11	v <- queue[head]12	head <- head + 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]

    26}27path <- rev(path)28cat("[", paste(path, collapse = ", "), "]\n", sep = "")
    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]

    27path <- rev(path)28cat("[", paste(path, collapse = ", "), "]\n", sep = "")29cat(dist[[as.character(dst)]], "\n", sep = "")
    values this step[1, 2, 4, 5, 6]stdout[1, 2, 4, 5, 6]path

  11. stdout ← 4

    28cat("[", paste(path, collapse = ", "), "]\n", sep = "")29cat(dist[[as.character(dst)]], "\n", sep = "")
    values this step4stdout4dist[6]

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

    28cat("[", paste(path, collapse = ", "), "]\n", sep = "")29cat(dist[[as.character(dst)]], "\n", sep = "")
    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

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