O problema do caminho mínimo e suas variantes

• Processo: 19/09476-4
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Data de Início da vigência: 01 de junho de 2019
• Data de Término da vigência: 31 de maio de 2020
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Matemática da Computação
• Pesquisador responsável: Carlos Eduardo Ferreira
• Beneficiário: Thiago Lima Oliveira
• Instituição Sede: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brasil
• Assunto(s): Teoria dos grafos Otimização combinatória Trajetória
• Palavra(s)-Chave do Pesquisador: Algoritmo de Bellman-Ford | Algoritmo de Dijkstra | caminhos mínimos | teoria dos grafos | Otimização combinatória

Resumo

Dentro da área de combinatória e teoria dos grafos um problema conhecido é o problema do caminho mínimo, ou seja, dado um grafo e dois vértices pertencentes a ele encontre o menor caminho entre os dois vértices. Em uma notação matemática o problema pode ser descrito como: dado um grafo G = (V, A) e dois vértices s e t tal que s, t pertencem a V e uma função custo c de A para os inteiros, queremos encontrar um conjunto de arestas S que leva de s a t tal que o somatório dos custos das arestas pertencentes a s seja mínimo. Este problema surge naturalmente em diversas áreas, como no cálculo da rota entre duas cidades ou na maneira de distribuir dados em uma rede de computadores, por isso este tema é de relevância na área. Neste trabalho será estudado além do problema do caminho mínimo, variações deste, como quando incluímos restrições ao número de arestas no caminho, ou outras. Por exemplo, no caminho S encontrado, adicionamos uma função R, das arestas para os inteiros, e colocamos a condição de que a soma de todos R(e) para todo e pertencente a S seja menor que um dado M. Também será analisado o caso em que é interessante procurar não somente o menor mas os K menores caminhos entre dois vértices. Este projeto será desenvolvido ao longo de 12 meses e o objetivo é aprender sobre o problema dos caminhos mínimos, pretendemos assim melhorar a base teórica e computacional em teoria dos grafos do aluno. Serão realizadas também reuniões semanais com o orientador para avaliar o desenvolvimento do projeto e tirar eventuais dúvidas.