Step 2 of 6
Shortest path with BFS
"What's the fewest number of steps from A to B?" When every edge costs the same (one move, one hop, one friend-of-a-friend), breadth-first search answers it. You saw BFS on trees as level-order traversal: it explores everything 1 step away, then everything 2 steps away, and so on. So the first time it reaches a vertex, it got there by a shortest route.
Graphs can have cycles, so BFS also needs to remember which vertices it has already reached, or it would go around in circles. A dist array does both jobs: -1 means "not reached yet", anything else is the shortest distance.
dist[start] = 0; queue = [start]
while queue not empty:
cur = pop front
for each neighbor nb with no dist yet:
dist[nb] = dist[cur] + 1; push nb
#include <iostream>
#include <queue>
#include <string>
#include <vector>
int main() {
std::vector<std::string> name = {"you", "ana", "ben", "cy", "dee", "eli"};
std::vector<std::vector<int>> friends = {{1, 2}, {0, 3}, {0, 3}, {1, 2, 4}, {3}, {}};
std::vector<int> dist(name.size(), -1);
std::queue<int> q;
dist[0] = 0;
q.push(0);
while (!q.empty()) {
int cur = q.front();
q.pop();
for (int nb : friends[cur]) {
if (dist[nb] == -1) { // first visit = shortest
dist[nb] = dist[cur] + 1;
q.push(nb);
}
}
}
for (std::size_t v = 1; v < name.size(); v++) {
std::cout << name[v] << ": " << dist[v] << "\n";
}
}
ana: 1
ben: 1
cy: 2
dee: 3
eli: -1
eli has no friends in this network, so BFS never reaches them and the distance stays -1.
Grids are graphs
A maze is a graph in disguise: each open cell is a vertex, connected to its up, down, left and right neighbors. You don't need to build an adjacency list; generate the neighbors on the fly with direction arrays:
const int dr[] = {-1, 1, 0, 0};
const int dc[] = {0, 0, -1, 1};
for (int d = 0; d < 4; d++) {
int nr = r + dr[d], nc = c + dc[d];
if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue; // off the grid
if (grid[nr][nc] == '#') continue; // wall
...
}
Keep dist as a 2D vector of the same shape as the grid, find S first, and return dist at E (-1 if never reached). The queue holds std::pair<int, int> positions.
Your turn: write int shortest_path(const std::vector<std::string>& grid) returning the fewest moves from S to E, moving through . cells (not #), or -1 if E can't be reached.