algoritmo

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