Mémoire de Maîtrise
DOI
https://doi.org/10.11606/D.45.2018.tde-20032018-003225
Document
Auteur
Nom complet
Diogo Haruki Kykuta
Adresse Mail
Unité de l'USP
Domain de Connaissance
Date de Soutenance
Editeur
São Paulo, 2018
Directeur
Jury
Ferreira, Carlos Eduardo (Président)
Franco, Álvaro Junio Pereira
Pina Junior, Jose Coelho de
Titre en portugais
Comparação de algoritmos para o Problema dos K Menores Caminhos
Mots-clés en portugais
Caminho mínimo
Grafos
Grafos dirigidos com peso nos arcos
K menores caminhos
Resumé en portugais
O Problema dos K Menores Caminhos é uma generalização do Problema do Menor Caminho, em que desejamos encontrar os K caminhos de menor custo entre dois vértices de um grafo. Estudamos e implementamos algoritmos que resolvem esse problema em grafos dirigidos, com peso nos arcos e que permitem apenas caminhos sem repetição de vértices na resposta. Comparamos seus desempenhos utilizando grafos do 9th DIMACS Implementation Challenge. Identificamos os pontos fortes e fracos de cada algoritmo, e propusemos uma variante híbrida dos algoritmos de Feng e de Pascoal. Essa variante proposta obteve desempenho superior aos algoritmos base em alguns grafos, e resultado superior a pelo menos um deles na grande maioria dos testes.
Titre en anglais
Comparison of algorithms for K Shortest Paths Problem
Mots-clés en anglais
Graphs
K shortest paths
Shortest path
Weighted directed graph
Resumé en anglais
The K-Shortest Path Problem is a generalization of the Shortest Path Problem, in which we must find the K paths between two vertices in a graph that have the lowest costs. We study some K-Shortest Path Problem algorithms applied to weighted directed graphs, allowing only paths with no repeated vertices. We compare empirically implementation of some algorithms, using instance graphs from the 9th DIMACS Implementation Challenge. We identify the strengths and weaknesses of each algorithm, and we propose a hybrid version of Feng's and Pascoal's algorithms. This proposed variant achieve better perfomance compared to both base algorithms in some graphs, and it is better than at least one of them in most cases.
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
2018-05-22
AVERTISSEMENT: Apprenez ce que sont des œvres dérivées
cliquant ici.