Exportar registro bibliográfico

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
  • Acesso à fonte
    How to cite
    A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas

    • ABNT

      ISOTANI, Shigueo; PINA JÚNIOR, José Coelho de. Algoritmos para caminhos mínimos. 2002.Universidade de São Paulo, São Paulo, 2002. Disponível em: < https://teses.usp.br/teses/disponiveis/45/45134/tde-20210729-125537/ >.
    • APA

      Isotani, S., & Pina Júnior, J. C. de. (2002). Algoritmos para caminhos mínimos. Universidade de São Paulo, São Paulo. Recuperado de https://teses.usp.br/teses/disponiveis/45/45134/tde-20210729-125537/
    • NLM

      Isotani S, Pina Júnior JC de. Algoritmos para caminhos mínimos [Internet]. 2002 ;Available from: https://teses.usp.br/teses/disponiveis/45/45134/tde-20210729-125537/
    • Vancouver

      Isotani S, Pina Júnior JC de. Algoritmos para caminhos mínimos [Internet]. 2002 ;Available from: https://teses.usp.br/teses/disponiveis/45/45134/tde-20210729-125537/

    Últimas obras dos mesmos autores vinculados com a USP cadastradas na BDPI:

    Digital Library of Intellectual Production of Universidade de São Paulo     2012 - 2021