Comparação de algoritmos para o Problema dos K Menores Caminhos (2018)
- Authors:
- Autor USP: KYKUTA, DIOGO HARUKI - IME
- Unidade: IME
- Sigla do Departamento: MAC
- DOI: 10.11606/D.45.2018.tde-20032018-003225
- Subjects: COMBINATÓRIA; OTIMIZAÇÃO COMBINATÓRIA
- Keywords: Caminho mínimo; Grafos; Grafos dirigidos com peso nos arcos; Graphs; K menores caminhos; K shortest paths; Shortest path; Weighted directed graph
- Agências de fomento:
- Language: Português
- Abstract: O Problema dos K Menores Caminhos é uma generalização do Problema do Menor Caminho, em que desejamos encontrar os K caminhos de menor custo entre dois vértices de um grafo. Estudamos e implementamos algoritmos que resolvem esse problema em grafos dirigidos, com peso nos arcos e que permitem apenas caminhos sem repetição de vértices na resposta. Comparamos seus desempenhos utilizando grafos do 9th DIMACS Implementation Challenge. Identificamos os pontos fortes e fracos de cada algoritmo, e propusemos uma variante híbrida dos algoritmos de Feng e de Pascoal. Essa variante proposta obteve desempenho superior aos algoritmos base em alguns grafos, e resultado superior a pelo menos um deles na grande maioria dos testes
- Imprenta:
- Data da defesa: 19.02.2018
- Status:
- Artigo publicado em periódico de acesso aberto (Gold Open Access)
- Versão do Documento:
- Versão publicada (Published version)
- Acessar versão aberta:
-
ABNT
KYKUTA, Diogo Haruki. Comparação de algoritmos para o Problema dos K Menores Caminhos. 2018. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 2018. Disponível em: https://teses.usp.br/teses/disponiveis/45/45134/tde-20032018-003225/. Acesso em: 16 abr. 2026. -
APA
Kykuta, D. H. (2018). Comparação de algoritmos para o Problema dos K Menores Caminhos (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de https://teses.usp.br/teses/disponiveis/45/45134/tde-20032018-003225/ -
NLM
Kykuta DH. Comparação de algoritmos para o Problema dos K Menores Caminhos [Internet]. 2018 ;[citado 2026 abr. 16 ] Available from: https://teses.usp.br/teses/disponiveis/45/45134/tde-20032018-003225/ -
Vancouver
Kykuta DH. Comparação de algoritmos para o Problema dos K Menores Caminhos [Internet]. 2018 ;[citado 2026 abr. 16 ] Available from: https://teses.usp.br/teses/disponiveis/45/45134/tde-20032018-003225/
Informações sobre a disponibilidade de versões do artigo em acesso aberto coletadas automaticamente via oaDOI API (Unpaywall).
Por se tratar de integração com serviço externo, podem existir diferentes versões do trabalho (como preprints ou postprints), que podem diferir da versão publicada.
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
