Teoria dos grafos caminho mais curto

Disponível somente no TrabalhosFeitos
  • Páginas : 7 (1606 palavras )
  • Download(s) : 0
  • Publicado : 11 de setembro de 2012
Ler documento completo
Amostra do texto
TEORIA DOS GRAFOS

CAMINHO MAIS CURTO


Leonardo Camanho Carneiro
Graduando em Sistemas de Informação
Universidade Salvador – UNIFACS – BA


Amaury Pereira de Oliveira
Graduando em Sistema de Informação
Universidade Salvador – UNIFACS – BA


Wilson Campos
Graduando em Sistema de Informação
Universidade Salvador – UNIFACS – BA



Resumo
Este artigo visater uma visão geral da teoria dos grafos focando no desenvolvimento de um algoritmo de caminho mais curto. Dentre os existentes, foi utilizado o algoritmo de Djikstra para exemplificar o menor caminho entre vários pontos distantes entre si. Para facilitar o entendimento foi utilizado um exemplo prático que seria a distância entre cidades e como resultado a obtenção do menor caminho entre cadacidade de Origem X Destino.

Palavras-chave

Grafo, distância, vértice, aresta, caminho, tempo, menor.

Introdução
O estudo de grafos é muito importante para resolução de diversas aplicações matemáticas. Sua definição geral consiste basicamente de um conjunto de vértices e um conjunto de arestas, onde uma aresta liga dois vértices pertencentes ao conjunto. Existe também uma função de defineessa relação entre os dois vértices. (BONDY, 1982). Podemos escrever: G=(Vg,Ag,Fg), onde :
1. G -> Grafo;
2. Vg -> Conjunto de vértices;
3. Ag -> Conjunto de arestas;
4. Fg -> Função que relaciona um elemento de A com um par de V. [pic]
G=(Vg,Ag,Fg)
Vg ={A,B,C,D}
Ag={a,b,c,d,e,f,g}
Fg= Ag -> (Vg, Vg) onde:
• Fg(a)=(A,B);
• Fg(b)=(A,B);
• Fg(c)=(A,C);• Fg(d)=(A,C);
• Fg(e)=(A,D);
• Fg(f)=(B,D);
• Fg(g)=(C,D);


Um grafo em que temos um valor para as arestas de forma a diferenciar o custo ao se percorrer cada aresta é chamado de grafo valorado. Os valores de um grafo podem representar diferentes informações, tais como distância, tempo ou custo financeiro, entre outros. Considerando a figura acima, podemos fazer uma analogiacom um mapa e distâncias percorridas. Cada vértice seria uma cidade e as arestas seriam os caminhos entre as cidades, cada aresta dessas teria sua distância em Km e assim teríamos um grafo com valores para podermos aplicar um algoritmo de menor caminho e descobrir a melhor rota.


Desenvolvimento
Os grafos podem ser utilizados em diversas áreas, como por exemplo: jogos, redes decomputadores, sistemas rodoviários, aéreos, ferroviários, dentre outros. O exemplo focado nesse trabalho é o de um sistema rodoviário, onde cada vértice é representado por uma cidade, e as arestas com seus valores representa a distância entre uma cidade e outra. O algoritmo de menor caminho, então, retorna como resultado, um grafo que representa o menor caminho partindo de um determinado ponto inicial, ouseja, caso eu entregue para o algoritmo uma grafo com vários caminhos entre São Paulo, Rio de Janeiro, Salvador, Curitiba, Belo Horizonte e quiser o menor caminho partindo de Curitiba, ele me retornaria um grafo com esse caminho.
Por exemplo, partindo de Curitiba:
[pic]
Grafo de Entrada


[pic]
Grafo após Djikstra

[pic]

Com esse entendimento o algoritmo pode ser demonstrado naseguinte forma. São definidas duas classes inicialmente que são: Vértice e Aresta. Temos na classe Vértice um nome para identificá-lo e o seu grau (número de arestas que lhe são incidentes) como atributos e seus respectivos métodos Gets e Sets, já na classe Aresta existem como atributos o nome para identificação, o Peso que representa o valor da aresta que nesse caso seria a distância entre as cidades,e um vértice de início e outro de fim que representam os vértices (Cidades) ligados por essa aresta e por fim seus métodos Gets e Sets.


[pic]
Classe Vértice
[pic]
Classe Aresta

Dessa forma temos o necessário para criar uma classe chamada GRAFO, nessa classe é onde se define os atributos vistos anteriormente, assim temos na referida classe uma lista de vértices e uma...
tracking img