Proposta de paralelização em GPUs CUDA do algoritmo MPS para resolução do problema de encontrar os K-Caminhos Mais Curtos Sem Repetições de Vértices em grafos direcionados e não direcionados

O Problema dos K-Caminhos mais Curtos sem Repetições de Vértices (K-Shortest Loopless Paths – KSLP) consiste em encontrar K | K > 1 caminhos, sem repetições de vértices, classificados em ordem crescente de distância, em um grafo G(V, E), no qual V representa o conjunto de vértices e E o conjunto dos arestas que os conecta. Dada a dificuldade de obter bom desempenho para solução do problema, este trabalho propõe a paralelização em GPUs CUDA do algoritmo mais veloz existente na literatura para o problema.