Caminhos Mínimos em Grafos

O problema de se encontrar caminhos mínimos em um grafo pode ser definido como a seguir:

Problema: dado um grafo $G(V,E)$, direcionado ou não-direcionado, e um vértice de origem $s$, encontrar a distância de $s$ para cada um dos vértices do grafo.

Note que o problema é encontrar a distância de um vértice $s$ para todos os outros vértices do grafo. Esse problema também é conhecido como o problema de se encontrar o "caminho mínimo de um para todos" em um grafo. Ao resolvê-lo, resolvemos também um problema mais simples: o problema de se encontrar o caminho mínimo entre dois vértices específicos de um grafo.

A distância de s para ele mesmo é zero.

Em um grafo com pesos nas arestas, a distância entre um vértice u e um outro vértice v é a soma dos pesos nas arestas do caminho que liga u a v. Em um grafo sem pesos nas arestas, essa distância é simplesmente o número de arestas no caminho entre u e v, ou seja, é como se cada aresta tivesse peso 1.

Para calcular o caminho mínimo entre um vértice de origem e todos os demais vértices do grafo, só precisamos fazer duas modificações simples no algoritmo de busca em largura:

Inicializar as distâncias iniciais de s para ele mesmo (zero, no caso) e de s para os demais vértices do grafo (distância infinita, inicialmente, pois não temos conhecimento algum sobre o grafo para dar uma estimativa melhor).
Quando um vértice w é visitado pela primeira vez, atualizamos sua distância (na verdade, essa é a distância de s até w, mas ela fica armazenada no próprio vértice w) como um mais a distância do vértice pelo qual w foi visitado.

Playground


			
				# Use este espaço para praticar o que você aprendeu nesta seção.
				
				# Basta digitar o código no espaço abaixo e clicar 'run'.