Título: Um estudo sobre o problema dos K caminhos mais curtos

Título alternativo: A study about the K shortest paths problem

Autoria de: Lorena Kerollen Botelho Tavares

Orientação de: Mayron Cesar de Oliveira Moreira

Presidente da banca: Mayron César de Oliveira Moreira

Primeiro membro da banca: Luiz Henrique Andrade Correia

Segundo membro da banca: Tiago Januario

Palavras-chaves: Algoritmos, Caminhos, Yen, Desvios, Clássicos.

Data da defesa: 09/03/2021

Semestre letivo da defesa: 2020-2

Data da versão final: 15/03/2021

Data da publicação: 15/03/2021

Referência: Tavares, L. K. B. Um estudo sobre o problema dos K caminhos mais curtos. 2021. 33 p. Trabalho de Conclusão de Curso (Graduação em Ciência da Computação Bacharelado)-Universidade Federal de Lavras, Lavras, 2021.

Resumo: O problema dos K caminhos mais curtos acíclicos (K-SP, do inglês K Shortest Loopless Paths Problem) consiste em encontrar, em uma rede direcionada valorada, um conjunto de K rotas, minimizando o caminho percorrido entre um ponto de origem e um ponto de destino. O objetivo deste trabalho é realizar um estudo sobre um algoritmo clássico da literatura para o K-SP, apresentando uma explicação detalhada do método e do conceito de algoritmo de desvio. Espera-se que o trabalho desenvolvido seja um facilitador para o entendimento do tema, tornando seu conteúdo mais compreensível para a comunidade acadêmica com interesse na resolução do problema e no algoritmo descrito.

Abstract: The K Shortest Loopless Paths Problem (K-SP) consists of finding, in a weighted network, a set of K routes, minimizing the path taken between an initial point and a terminal point. This work aims to study a classic literature algorithm for K-SP, presenting a detailed explanation of the method and the concept of deviation algorithm. We expect that the work developed will help understand the theme, making its content more understandable for academic community interested in the problem resolution and the algorithm described here.

URI: sip.prg.ufla.br/publico/trabalhos_conclusao_curso/acessar_tcc_por_curso/
ciencia_da_computacao/20202201611008

URI alternaviva: repositorio.ufla.br/handle/1/47502

Curso: G010 - CIÊNCIA DA COMPUTAÇÃO (BACHARELADO)

Nome da editora: Universidade Federal de Lavras

Sigla da editora: UFLA

País da editora: Brasil

Gênero textual: Trabalho de Conclusão de Curso

Nome da língua do conteúdo: Português

Código da língua do conteúdo: por

Licença de acesso: Acesso aberto

Nome da licença: Licença do Repositório Institucional da Universidade Federal de Lavras

URI da licença: repositorio.ufla.br

Termos da licença: Acesso aos termos da licença em repositorio.ufla.br

Detentores dos direitos autorais: Lorena Kerollen Botelho Tavares e Universidade Federal de Lavras

Baixar arquivo