% Assumption: the weight of all edges is exactly 1
% G is the graph
% a the starting node
% z the ending node
% for all nodes v in G, v.prev = NULL

% The algorith computes the shortest path from a to z in G
% When the algorithm stops, the shortest path is defined in reverse
% order by z, z.prev, z.prev.prev, .....

% shortest_path is a (slightly) modified BFS from a
shortest_path(G,a,z) {
  Q = EmptyQueue()
  mark(a)
  enqueue(Q,a)
  while not Empty(Q) {
    w = dequeue(Q)
    if w = z then STOP;
    for each v in AdjSet(w) {
       if not marked(v) {
          v.prev = w
          push(Q,w)
       }
    }
  }
}