Mémoire de Maîtrise
DOI
https://doi.org/10.11606/D.45.2002.tde-20210729-125537
Document
Auteur
Nom complet
Shigueo Isotani
Adresse Mail
Unité de l'USP
Domain de Connaissance
Date de Soutenance
Editeur
São Paulo, 2002
Directeur
Titre en portugais
Algoritmos para caminhos mÃnimos
Mots-clés en portugais
Algoritmos E Estruturas De Dados
Resumé en portugais
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
Titre en anglais
not available
Resumé en anglais
not available
AVERTISSEMENT - Regarde ce document est soumise à votre acceptation des conditions d'utilisation suivantes:
Ce document est uniquement à des fins privées pour la recherche et l'enseignement. Reproduction à des fins commerciales est interdite. Cette droits couvrent l'ensemble des données sur ce document ainsi que son contenu. Toute utilisation ou de copie de ce document, en totalité ou en partie, doit inclure le nom de l'auteur.
Date de Publication
2021-07-29
AVERTISSEMENT: Apprenez ce que sont des œvres dérivées
cliquant ici.