O problema do caminho mais curto : algoritmos de Dijkstra, D' Esopo - Pape, SLF e SLFT

• Ano de defesa: 2008
• Autor(a) principal: Méndez, Yasmín Salazar
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Programa de Pós-graduação em Engenharia de Produção; Estratégia-Apoio Logístico-Tecnologia e Trabalho
• Palavras-chave em Português: Problema do caminho mais curto; Redes; Grafos; Algoritmos; Rotulação permanente; Correção de rotulação; Problema del camino más corto; Fijación; Corrección de etiquetas; CNPQ::ENGENHARIAS::ENGENHARIA DE PRODUCAO
• Link de acesso: https://app.uff.br/riuff/handle/1/18012

En este trabajo se aborda el problema del camino más corto. Se presenta una descripción general del problema del camino más corto, su formulación y algunas aplicaciones, además de algunos conceptos de la teoría de grafos, redes y algoritmos, que son considerados como fundamentales para el estudio de este tema. El problema del camino más corto es tratado en esta disertación haciendo énfasis en los algoritmos del método de etiquetado. Para establecer ventajas en términos de rapidez de respuesta fueron evaluados con redes de gran tamaño cuatro algoritmos: Dijkstra con heap binario (fijación de etiquetas), D Esopo Pape, Small Label - First (SLF) y Small Label First - Threshold (SLFT) (corrección de etiquetas). Los resultados obtenidos muestran que el algoritmo que ofrece el menor tiempo de respuesta es Dijkstra con heap binario, seguido por SLFT, SLF e D Esopo Pape.