Teoria dos grafos caminho mais curto

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 visa ter 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 cada cidade 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 define essa 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 analogia