Return to search

K-menores caminhos / k-shortest paths

Tratamos da generalização do problema da geração de caminho mínimo, no qual não apenas um, mas vários caminhos de menores custos devem ser produzidos. O problema dos k-menores caminhos consiste em listar os k caminhos de menores custos conectando um par de vértices. Esta dissertação trata de algoritmos para geração de k-menores caminhos em grafos simétricos com custos não-negativos, bem como algumas implementações destes. / We consider a long-studied generalization of the shortest path problem, in which not one but several short paths must be produced. The k-shortest (simple) paths problem is to list the k paths connecting a given source-destination pair in the digraph with minimum total length. This dissertation deals with k-shortest simple paths algorithms designed for nonnegative costs, undirected graphs and some implementations of them.

Identiferoai:union.ndltd.org:usp.br/oai:teses.usp.br:tde-14072009-185725
Date16 June 2009
CreatorsPisaruk, Fabio
ContributorsPina Junior, Jose Coelho de
PublisherBiblioteca Digitais de Teses e Dissertações da USP
Source SetsUniversidade de São Paulo
LanguagePortuguese
Detected LanguagePortuguese
TypeDissertação de Mestrado
Formatapplication/pdf
RightsLiberar o conteúdo para acesso público.

Page generated in 0.002 seconds