Algoritmos para caminhos mínimos (2002)
- Authors:
- Autor USP: ISOTANI, SHIGUEO - IME
- Unidade: IME
- Sigla do Departamento: MAC
- Assunto: ALGORITMOS E ESTRUTURAS DE DADOS
- Language: Português
- Abstract: 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
- Imprenta:
- Data da defesa: 21.03.2002
-
ABNT
ISOTANI, Shigueo. Algoritmos para caminhos mínimos. 2002. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 2002. Disponível em: https://teses.usp.br/teses/disponiveis/45/45134/tde-20210729-125537/. Acesso em: 18 abr. 2024. -
APA
Isotani, S. (2002). Algoritmos para caminhos mínimos (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de https://teses.usp.br/teses/disponiveis/45/45134/tde-20210729-125537/ -
NLM
Isotani S. Algoritmos para caminhos mínimos [Internet]. 2002 ;[citado 2024 abr. 18 ] Available from: https://teses.usp.br/teses/disponiveis/45/45134/tde-20210729-125537/ -
Vancouver
Isotani S. Algoritmos para caminhos mínimos [Internet]. 2002 ;[citado 2024 abr. 18 ] Available from: https://teses.usp.br/teses/disponiveis/45/45134/tde-20210729-125537/
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
