Caminho Mínimo Guloso

1. Definição e formulação do problema
Os problemas de caminho mais curto (problemas do caminho mínimo) com um só objetivo são fundamentais e frequentes quando se estudam problemas em redes, por exemplo, de transportes ou de comunicações. Este problema surge quando se pretende determinar o caminho mais curto, mais barato ou mais fiável, entre um ou vários pares de nós de uma rede.

Estes problemas surgiram a partir de adaptações a uma grande variedade de problemas práticos, não só como modelos únicos mas também como subproblemas de problemas mais complexos. Por exemplo, surgiram nas indústrias de telecomunicações e de transportes sempre que se pretendia enviar uma mensagem, ou um veículo, entre dois locais geograficamente distantes, o mais rápido ou o mais barato possível.

O planejamento do tráfego urbano fornece um outro exemplo importante : os modelos utilizados para o cálculo do fluxo de tráfego padrão são problemas de otimização não linear, ou modelos de equilíbrio complexos. Contudo, a maioria das abordagens algorítmicas para determinar tráfegos urbanos padrão consiste, sob hipóteses simplificadoras, em resolver um grande número de problemas de caminho mais curto como subproblemas (um para cada par de nós origem−destino na rede).
Existem três tipos de problemas de caminho mais curto :
• de um nó para outro,
• de um nó para todos os outros (árvore dos caminhos mais curtos),
• entre todos os pares de nós.

Os dois primeiros tipos são identificados como problema de caminho mais curto de uma única origem, que recai no algoritmo de Dijkstra para resolver este problema. E o outro como problema de caminho mais curto entre todos os pares de nós, onde tem o algoritmo Warshall Floyd para resolver este problema.

Algoritmo de Dijsktra

O algoritmo de Dijkstra é um algoritmo guloso, ou seja, toma a decisão que parece ótima no momento. Para a teoria dos grafos uma "estratégia gulosa" é conveniente já que sendo um menor caminho entre 2