Detalhes bibliográficos
| Ano de defesa: |
2002 |
| Autor(a) principal: |
Isotani, Shigueo |
| Orientador(a): |
Não Informado pela instituição |
| Banca de defesa: |
Não Informado pela instituição |
| Tipo de documento: |
Dissertação
|
| Tipo de acesso: |
Acesso aberto |
| Idioma: |
por |
| Instituição de defesa: |
Biblioteca Digitais de Teses e Dissertações da USP
|
| Programa de Pós-Graduação: |
Não Informado pela instituição
|
| Departamento: |
Não Informado pela instituição
|
| País: |
Não Informado pela instituição
|
| Palavras-chave em Português: |
|
| Link de acesso: |
https://teses.usp.br/teses/disponiveis/45/45134/tde-20210729-125537/
|
Resumo: |
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 |
