Run breadth-first search from both ends at once and stop where the two frontiers meet: two small balls instead of one big one.
This interactive visualization needs JavaScript.