Achar o caminho mais curto com a busca em largura

A primeira vez que se chega é a mais curta

A aula da busca em largura já deixou a pista: como ela explora camada por camada, a primeira vez que toca um vértice é sempre pelo caminho com o menor número de passos. Falta transformar essa propriedade num caminho concreto que você possa mostrar. O truque é simples e elegante: toda vez que a busca descobre um vértice novo através de um vizinho, ela anota quem foi esse vizinho. É como deixar uma trilha de migalhas. Cada vértice passa a saber de onde veio, e essa anotação, feita uma única vez no momento da descoberta, é tudo que você precisa para refazer o trajeto depois.

Pense num carteiro que espalha a notícia de casa em casa. Cada casa que recebe o recado anota de qual vizinha ouviu primeiro. Quando você quer saber o caminho da casa de origem até uma casa qualquer, basta perguntar a essa casa quem lhe contou, depois perguntar à casa anterior a mesma coisa, e assim por diante, até chegar na origem. Você anda de trás para frente pela trilha de migalhas. Como cada casa ouviu primeiro pela rota mais curta (a notícia se espalha em ondas, como na busca em largura), o caminho reconstruído é o mais curto possível em número de passos.

Guardar de onde cada um veio

Na prática, você acrescenta à busca em largura uma tabela que associa cada vértice ao seu predecessor, o vértice de onde ele foi descoberto. O início não tem predecessor, ele é o ponto de partida. A cada vizinho novo que entra na fila, você grava nessa tabela: o predecessor deste vizinho é o vértice atual. Quando a busca termina, ou quando ela alcança o destino, você reconstrói o caminho começando no destino, olhando seu predecessor, depois o predecessor do predecessor, até cair no início. Essa sequência sai de trás para frente, então basta invertê-la para ter o caminho na ordem natural, do começo ao fim.

fila <- [inicio]
visitados <- {inicio}
veio_de <- {}         // predecessor de cada vértice
enquanto fila não está vazia faça
  atual <- tira da frente da fila
  para cada vizinho de atual faça
    se vizinho não está em visitados então
      adiciona vizinho em visitados
      veio_de[vizinho] <- atual   // anota a migalha
      coloca vizinho no fim da fila
    fim
  fim
fim
// reconstruir do destino até o início:
caminho <- []
passo <- destino
enquanto passo existe faça
  coloca passo no início de caminho
  passo <- veio_de[passo]
fim
escreva(caminho)

A tabela veio_de guarda o predecessor de cada vértice. No fim, seguir de destino até início e inverter dá o caminho mais curto.

Um labirinto é só um grafo disfarçado: cada casa livre é um vértice, e há uma aresta entre casas vizinhas que não têm parede entre elas. Rodar a busca em largura a partir da casa inicial encontra o menor número de passos até a saída, e a trilha de predecessores devolve o caminho exato. É assim que aplicativos de rota calculam trajetos em grades e que jogos movem inimigos até o jogador. O mesmo raciocínio responde o grau de separação: numa rede de amizades, a busca em largura a partir de uma pessoa acha em quantos apertos de mão você chega a outra, e por qual sequência de amigos.

Cuidados ao reconstruir o caminho

Dois cuidados evitam a maioria dos erros. O primeiro é lembrar que o caminho sai invertido: você o monta do destino para o início, então precisa virá-lo antes de mostrar, ou ir colocando cada passo no começo da lista, como no exemplo. Esquecer de inverter é um deslize comum e faz o programa dizer que a rota começa no destino. O segundo é tratar o caso de não existir caminho: se o destino nunca aparece no conjunto de visitados, ele é inalcançável, e a reconstrução deve avisar isso em vez de tentar seguir uma trilha que não existe. Vale ainda lembrar que essa técnica dá o menor caminho em passos iguais; quando as arestas têm pesos diferentes (distâncias, tempos), a busca em largura simples não basta e entram algoritmos de caminho mínimo ponderado, um assunto mais avançado.