Given the following algorithm for a breadth first search of a graph, using queues.

Code:

Set the distances for each node to infinity
Enqueue the starting node, and set distance of the node to zero.
While the queue is not empty {
Dequeue the first element in the queue
Enqueue all the nodes adjacent to the node we just dequeued
Update the distances of each of the nodes we just enqueued
}

Prove that for any two elements in the queue u and v. $\displaystyle |dist(u) - dist(v)| \leq 1$. A hint provided to me was to prove a stronger statement about the ordering of the elements in the queue.

So, I thought if I could prove via induction that if u is closer to the front than v in queue then $\displaystyle dist(u) \leq dist(v)$, and that $\displaystyle |dist(front) - dist(back)| \leq 1$. But I am having troubles with it.

Is my idea good, or is there an easier property I could prove? If what I have is good, how could I prove it?

Thanks in advance!