Caminho Mínimo em Redes

O uso do algoritmo de Dijkstra para encontrar o caminho mais curto entre dois nós

O problema de encontrar o caminho mais curto entre dois nós de um grafo ou uma rede é um dos clássicos da ciência da computação. Este problema consiste, genericamente, em encontrar o caminho de menor custo entre dois nós da rede, considerando a soma dos custos associados aos arcos percorridos.

O problema do caminho mínimo se adapta a diversas situações práticas. Em roteamento, por exemplo, pode-se modelar os nós do grafo como cruzamentos, os arcos como vias, e os custos associados aos arcos correspondem ao tempo de trajeto ou distância percorrida, e a solução será o caminho mais curto ou o caminho mais rápido entre dois pontos. Em redes de computadores, os nós poderão representar equipamentos diversos, os arcos correspondem a trechos de cabeamento, e os custos poderão estar associados à taxa máxima de transmissão de dados. Neste caso, a solução será a rota de transmissão mais rápida. Outras possibilidades de aplicação incluem quaisquer problemas envolvendo redes ou grafos em que se tenha grandezas (distâncias, tempo, perdas, ganhos, despesas) que se acumulem linearmente ao longo do percurso da rede.

O mais famoso dos algoritmos para resolver o problema de caminho mínimo em redes é o algoritmo de Dijkstra, proposto em 1959. Este algoritmo apenas funciona se os custos associados aos arcos não forem negativos, mas isso não é muito importante na maioria dos problemas práticos pois, em geral, os custos associados aos arcos são grandezas fisicamente mensuráveis. Assim, o algoritmo de Dijkstra acaba por se constituir no método de solução de problemas de caminho mínimo mais empregado na prática.

O algoritmo considera um grafo G, composto por um conjunto de nós, denominado N, e um conjunto de arcos denominado A. Além disto, são conhecidos dois nós pertencentes a N, denominados o e d, que são respectivamente a origem e o destino. Os nós são divididos em três grupos: os já visitados (conjunto V), os candidatos ou de fronteira (conjunto F) e os nunca visitados ou "desconhecidos" (conjunto D). O conjunto V é inicializado para conter apenas o nó o. Os vizinhos imediatos de o são colocados no conjunto F, sendo registrados os custos para atingí-los a partir de o, e os demais inicialmente pertencem ao conjunto D. A cada passo do algoritmo, os nós de F são verificados para determinar qual seria a melhor opção para expandir a pesquisa. Será escolhido e transferido para V aquele nó cujo custo acumulado seja o menor dentre os candidatos, e seus vizinhos serão então transferidos do conjunto D para o conjunto F. A pesquisa para quando o nó d for alcançado ou quando não houver mais nós a percorrer (neste caso, não existe caminho viável entre o e d).

Figura 1 – Rede e caminho mínimo (1-2-5-7, custo 12 unidades)

Observando a rede da Figura 1, vamos executar passo a passo o algoritmo para encontrar o menor caminho entre o nó 1 e o nó 7. Vamos usar a notação nó (custo, nó anterior) para indicar a situação de cada nó visitado. Por exemplo 7(8, 3) significa que o nó 7 foi alcançado com custo total igual a 8, a partir do nó número 3.

1 – Inicialmente, V = {1(0,0)}, o custo para atingir o único nó visitado (1) é zero. A fronteira é F = {2, 3}(os vizinhos dos nós de V), e o conjunto de desconhecidos D = {4, 5, 6, 7}(todos os outros nós).

2 -Verificando os nós contidos em F, observamos que, partindo de 1, pode-se chegar a 2, com custo 2, ou a 3, com custo 3. Escolhemos o arco 1-2, pois é o de menor custo dentre os que se apresentam no momento. Assim, teremos V = {1(0,0), 2(2,1)}, ou seja, já chegamos ao nó 2 com custo 2. Os demais conjuntos ficam F = {3, 4, 5}(eliminamos o 2, já visitado, e incluímos seus vizinhos imediatos, 4 e 5) e D = {6, 7}.

3 – Novamente partindo dos nós contidos em F, temos as seguintes opções: 3 (custo 3), 4 (custo 5, ou seja, 2 até o nó 2, mais 3 do arco 2-4), 5 (custo 7). Escolhemos o nó 3, pelo menor custo acumulado. Os conjuntos ficam V = {1(0,0), 2(2,1), 3(3,1)}, F = {4, 5, 6}e D = {7}.
4 – Outra verificação dos nós contidos em F: 4(4,3), 5(7,2), 6(9,3). Observe que o nó 4 pode ser alcançado tanto a partir do nó 3, com custo 4, quanto a partir do nó 2, com custo 5. Damos preferência, naturalmente, ao caminho mais curto, passando por 3. A escolha é pelo nó 4, e os conjuntos ficam V = {1(0,0), 2(2,1), 3(3,1), 4(4,3)}, F = {5, 6}e D = {7}.

5 – Mais um passo, verificando os nós de F, temos 5(7, 2) e 6(9, 3). Escolhemos o nó 5, e os conjuntos ficam V = {1(0,0), 2(2,1), 3(3,1), 4(4,3), 5(7,2)}, F = {6,7} e D = ø. Note que novamente o nó 5 pode ser alcançado por dois caminhos diferentes, e optamos pelo de menor custo acumulado.

6 – Analisando agora os nós 6 e 7, temos 6(9, 3) e 7(12, 5). O escolhido agora é o nó 6, e temos os conjuntos V = {1(0,0), 2(2,1), 3(3,1), 4(4,3), 5(7,2), 6(9,3)}, F = {7}e D = ø.

7 – Finalmente, verificamos novamente o conjunto F, e constatamos duas alternativas para chegar ao nó 7: a partir de 5, com custo 12, e a partir de 6, com custo 13. Optamos pelo caminho mais curto, e os conjuntos ficam V = {1(0,0), 2(2,1), 3(3,1), 4(4,3), 5(7,2), 6(9,3), 7(12,5)}, F = ø e D = ø .

8 – O algoritmo é interrompido quando se consegue inserir o nó de destino (7) no conjunto V, ou quando não há mais nós a verificar no conjunto F. Quando a segunda opção ocorre sem que o nó de destino tenha sido alcançado, isso significa que não existe um caminho viável entre os nós de origem e destino dados. No exemplo, isso não ocorreu.

9 – O caminho mínimo obtido pode ser recuperado de trás para a frente, observando, a partir do nó de destino, qual é o nó anterior. A seqüência, no caso do exemplo, é 7-5-2-1, ou seja, o caminho de menor custo entre 1 e 7 é 1-2-5-7, com custo total de 12.

O critério de seleção do próximo nó é típico dos algoritmos ditos gulosos (greedy), e embora seja difícil acreditar à primeira vista, o método realmente conduz à escolha do caminho de menor custo.

Em uma rede de maiores dimensões, a expansão da pesquisa pode ser visualizada com a ajuda de um GIS. O padrão de expansão se assemelha a um "borrão de tinta", pois tende a se espalhar de forma aproximadamente circular em torno do ponto de origem (Figura 2).

Figura 2 – Padrão de expansão da pesquisa no algoritmo de Dijkstra (cada variação de cor corresponde a 5.000 objetos visitados)

Na implementação de pesquisas de caminho mínimo em GIS, existe a complexidade adicional de selecionar e extrair os dados necessários a cada passo a partir do banco de dados geográfico. A opção natural para a implementação deste recurso em um GIS seria fazer a recuperação dos dados à medida em que sejam demandados pelo algoritmo, na esperança de recuperar o mínimo possível de informações, e ao mesmo tempo restringire o uso da memória principal ao mínimo indispensável. O algoritmo oferece uma oportunidade ideal para isto, exatamente no ponto em que o nó é transferido para o conjunto V e sua vizinhança é colocada no conjunto F. Infelizmente, isto implica em uma performance bem mais baixa que a que poderia ser alcançada se toda a rede estivesse disponível em uma estrutura de dados apropriada, na memória principal do computador.

Existem situações práticas, em determinadas aplicações, em que os tempos de resposta que se pode conseguir na solução de problemas de caminho mínimo em SIG simplesmente se tornam inaceitáveis, pois o GIS é obrigado, em cada passo, a buscar os nós que entram para o conjunto F usando uma seleção no banco de dados geográfico, o que é relativamente lento se comparado com os tempos de recuperação de dados que estão na memória principal do computador.

Uma alternativa consiste em implementar o algoritmo de Dijkstra em C ou outra linguagem de programação otimizada, externamente ao GIS, preparando-o de modo que possa utilizar dados extraídos de tempos em tempos da base geográfica e produzir resultados que possam ser realimentados ao GIS. Desta forma, é possível extrair toda a velocidade de processamento possível para o algoritmo de Dijkstra, usando todos os recursos de estruturação de dados e otimização de código disponíveis. A principal limitação desse esquema é quanto à freqüência de atualização do grafo na base geográfica. É pouco prático fazer a exportação do grafo para arquivos externos constantemente, pois esta operação pode ser a mais demorada. Assim, essa solução é mais adequada nos casos em que a rede não é constantemente modificada.

O algoritmo de Dijkstra foi desenvolvido para resolver problemas em redes genéricas. No caso de uma rede de circulação de trânsito ou de qualquer rede em que os nós e arcos possam ser geograficamente localizados, é interessante utilizar a informação de que dispomos a respeito da distribuição geográfica da rede. A heurística de Hart-Nillson-Raphael propõe que esta escolha do próximo nó seja feita de modo a privilegiar não o menor custo acumulado, como no caso do exemplo, mas a menor soma entre o custo acumulado e a distância euclidiana (em linha reta) do nó candidato até o nó destino. Esta estratégia consegue reduzir significativamente o número de nós visitados, modificando o padrão de expansão da pesquisa do já citado "borrão de tinta" para um padrão direcional, que caminha mais diretamente para o nó de destino (Figura 3). É importante ressaltar que a solução encontrada com essa alternativa é rigorosamente a mesma.

Figura 3 – Padrão de expansão da pesquisa no algoritmo de Dijkstra usando a heurística de Hart-Nillson-Raphael (cada variação de cor corresponde a 5.000 objetos visitados)

Clodoveu Davis é engenheiro civil, doutor em Ciência da Computação e Assessor de Desenvolvimento e Estudos da Prodabel – Empresa de Informática e Informação do Município de Belo Horizonte. E-mail: cdavis@uol.com.br