Disertación de Maestría
DOI
https://doi.org/10.11606/D.45.2002.tde-20210729-125537
Documento
Autor
Nombre completo
Shigueo Isotani
Dirección Electrónica
Instituto/Escuela/Facultad
Área de Conocimiento
Fecha de Defensa
Publicación
São Paulo, 2002
Director
Título en portugués
Algoritmos para caminhos mÃnimos
Palabras clave en portugués
Algoritmos E Estruturas De Dados
Resumen en portugués
O problema do caminho mÃnimo consiste em: dados um grafo (V, A), uma função comprimento c de A em Z> ou = e um vértice s encontrar um caminho de comprimento mÃnimo de s até t, para cada vértice t em V. Desde 1959, quase todos os desenvolvimentos teóricos para esse problema têm se baseado no algoritmo de Dijkstra [11]. Foram desenvolvidas várias estruturas de dados que aumentam a eficiência desse algoritmo. Porém, qualquer implementação do mesmo examina os vértices em ordem crescente de distância a partir do vértice inicial s. Portanto, ocorre uma ordenação implÃcita dos vértices de acordo com essas distâncias. Assim, no modelo de comparação-adição, qualquer implementação deste algoritmo consome tempo (m + n log n), onde n é o número de vértices e m é o número de arcos do grafo dado. Para grafos simétricos e comprimentos em Z>, Thorup [39] projetou um algoritmo, no modelo RAM, que consome tempo e espaço O(m + n). O algoritmo utiliza uma decomposição hierárquica do grafo e 'bucketing' para identificar eficientemente conjuntos de vértices que podem ser examinados em qualquer ordem, evitando assim, o 'gargalo' da ordenação. Nesta dissertação são descritos e implementados vários algoritmos para o poblema do caminho mÃnimo, inclusive os mencionados acima. Ao final, é feita uma análise experimental das implementações realizadas
Título en inglés
not available
Resumen en inglés
not available
ADVERTENCIA - La consulta de este documento queda condicionada a la aceptación de las siguientes condiciones de uso:
Este documento es únicamente para usos privados enmarcados en actividades de investigación y docencia. No se autoriza su reproducción con finalidades de lucro. Esta reserva de derechos afecta tanto los datos del documento como a sus contenidos. En la utilización o cita de partes del documento es obligado indicar el nombre de la persona autora.
Fecha de Publicación
2021-07-29