Ciência da Computação na prática — Teoria dos Grafos: Caminho mais curto
Vamos imaginar uma situação hipotética:
Digamos que só exista uma companhia aérea em todo o mundo. Ela faz todos os voos entre todas as cidades do planeta. Não existem voos diretos entre todas as cidades, ou seja, você não consegue sair de todos os aeroportos e chegar diretamente no seu destino, sem escalas. Haverão voos diretos, mas também haverão voos com escalas.
Digamos também que o preço é único para cada destino, não importando o número de escalas que o voo faça. Um voo sem escalas custa o mesmo que um outro com 10 escalas. Imaginemos também que não há tempo entre as escalas e os voos nunca se atrasam nem se adiantam. Ou seja, ao chegar numa escala, você imediatamente é embarcado para a próxima escala (ou para o destino final). Tudo isto é apenas para simplificar o problema e entender melhor o funcionamento do algoritmo que iremos analisar neste artigo.
Dadas essas condições, como respondemos à seguinte pergunta:
Dados um aeroporto de origem A e um aeroporto de destino X, qual é o caminho entre esses dois aeroportos com menos escalas?
Caminho mais curto ao resgate
No artigo anterior, eu apresentei o algoritmo de busca em largura em grafos. Se, por acaso você não leu, pode consultar aqui.
Uma das características do algoritmo de busca em largura é que, ao final de sua execução, ele encontra o caminho mais curto entre o vértice origem e os outros vértices.
Vamos relembrar aqui a definição que eu coloquei no artigo anterior, mas agora com o grifo necessário:
Dado um Grafo G=(V,E) e um vértice de origem s, o algoritmo da busca em largura vai explorar sistematicamente todas as arestas de G até descobrir todos os vértices de G a partir de s. Além disso, o algoritmo também produz uma árvore de extensão, na qual qualquer vértice v acessível a partir de s, o caminho da árvore de s até v corresponde ao “caminho mais curto” entre s e v.
O segredo da árvore de extensão está no algoritmo que escrevemos para realizar a busca em largura, com destaque na linha 91:
Para cada nó encontrado que ainda não foi visitado, colocamos num mapa cujo índice é o próprio vértice que está sendo visitado, o vértice ancestral, ou seja, o vértice anterior o qual foi possível atingir o vértice atual através de uma aresta entre ambos.
Esse mapa, que é construído no momento da primeira visita ao vértice, será aquele que usaremos para encontrar o caminho mais curto entre dois vértices, iniciando com o vértice de origem s.
Para permitir a impressão do caminho mais curto entre dois vértices, iremos modificar levemente o algoritmo, adicionando um novo parâmetro, que nos permitirá consultar os ancestrais após a execução do BFS.
Assim, o nosso algoritmo modificado parecerá com o código abaixo (também escrito em Kotlin).
Adicionamos também uma função que, dados dois vértices e o mapa de ancestrais (que é construído durante a execução do BFS), encontra e imprime o caminho mais curto entre os dois vértices.
Esse caminho começa basicamente pelo destino e vai encontrando qual o nó ancestral desse destino. Encontrado o nó ancestral, o algoritmo é chamado recursivamente para a origem e esse nó ancestral. O algoritmo termina quando o nó ancestral é a origem ou então quando chegou num nós que não tem ancestral, o que indica que não há caminho entre os dois nós origem e destino.
Usando o grafo final após a execução do BFS, teremos a seguinte situação:
Assim, se quisermos saber o caminho mais curto entre o vértice s e o vértice u, o algoritmo, ao final da execução, imprimirá
Para fazer o teste que o algoritmo realmente funciona, tente chegar ao mesmo vértice de destino fazendo outro caminho e veja se o caminho é maior ou menor.
Uma observação: Vale lembrar que os nossos grafos, até o momento, não tem peso nas arestas, ou, se assim preferirmos, todas as arestas tem peso 1. Assim, o peso das mesmas não é considerado em nossos algoritmos (Grafos com pesos nas arestas podem ser abordados em um artigo posterior).
O problema dos aeroportos
Ok, depois de ver o resultado num algoritmo genérico, como ficaria nosso problema inicial?
Vamos imaginar que ao invés de labels como r, s, t, u, cada vértice seja um aeroporto e cada aresta seja um voo existente entre as duas cidades. Ao final da mesma execução do algoritmo BFS, teríamos o seguinte resultado:
As linhas mais grossas correspondem aos vértices escolhidos pelo algoritmo e o número dentro do nó corresponde à distância do nó até a origem.
Assim, se quiséssemos saber o caminho mais curto entre Nova York e Tokyo, por exemplo, saberíamos que Tokyo está a uma distância de 3 de Nova York e o caminho mais curto teria como resultado:
Concluímos mais um algoritmo e algumas aplicações mais concretas começam a aparecer. O exemplo acima é bem tosco, mas para que fique mais realista, iremos precisar incluir novos elementos aos nossos grafos, como pesos e direção nas arestas. Espero poder continuar aprofundando esses assuntos.
