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