Problema com grafos

Problema do Caminho Mais Curto
Componentes: Bruno, Guilherme e Maikel Losekann

Como tudo começou

O uso de grafos para a resolução de tais problemas, como o problema do caminho mais curto, do caixeiro viajante, etc., quando no século XVIII, o povo da cidade de Konigsberg (cidade Prussa) escreveu a Euler colocando-lhe a seguinte questão:
“ A nossa cidade é atravessada por um rio no qual existem 2 ilhas e sete pontes. É possível realizar um percurso através da cidade que inclua as sete pontes sem atravessar a mesma ponte duas vezes?”

Para resolver este problema, aparentemente simples, Euler considerou 4 pontos (dois pontos representando as margens e outros dois representando as ilhas) e 7 linhas (representando as pontes), obtendo:

Os esquemas do tipo do representado na figura acima constituem representações gráficas de grafos. Neste caso, temos uma representação de um grafo não orientado, o que significa que cada uma das linhas pode ser percorrida em ambos os sentidos. Mais precisamente, temos um multigrafo não orientado, pois temos mais de uma ligação entre dois pontos.

Problema do Caminho Mais curto

Considere um grafo orientado a G agora com dois nodos fixos v1 e v2 haverá em geral vários caminhos possíveis, o problema do caminho mais curto consiste em identificar o caminho de menor custo entre todos os caminhos possíveis.
Seja G=(X,A) um grafo, orientado ou não. É possível associar um comprimento (custo ou peso) a cada um dos elementos de A. Assim, define-se comprimento de um caminho (ou cadeia) como a soma dos comprimentos dos arcos (ou arestas) incluídos no referido caminho.
As aplicações do caminho mais curto são varias, a função que representa a aresta pode ser baseada em vários fatores como número de ligações, tráfego, atraso, distancia física, qualidade dos dados recebidos, custo canal, ou algum outro fator.
Achar o melhor caminho é encontrar o caminho com menos custo entre dois pontos de interesse com relação à função de custo