Resumen

El problema del grafo multietapa es un tipo especial de problema de camino más corto de origen único y destino único. Es difícil, e incluso imposible, resolver los grafos multietapa a gran escala utilizando una sola máquina con algoritmos secuenciales. Existen muchos sistemas distribuidos de computación de grafos que pueden resolver este problema, pero a menudo están diseñados para grafos grandes en general, sin considerar las características especiales de los grafos multietapa. Este documento propone DMGA (Algoritmo de Grafo Multietapa Distribuido) para resolver el problema de camino más corto de acuerdo con las características estructurales de los grafos multietapa. El algoritmo primero asigna el grafo a un conjunto de nodos de computación para almacenar los vértices de la misma etapa en el mismo nodo de computación. A continuación, DMGA calcula los caminos más cortos entre cualquier par de vértices de inicio y final dentro de una partición mediante el algoritmo clásico de programación dinámica. Por último, el camino más corto global se calcula intercambiando subresultados entre nod

• Materias:Colonias de abejas artificiales Inteligencia artificial Patrón espacial Innovación de la comunicación Algoritmo de red neuronal
• Subjects:Artificial bee colonies Artificial intelligence Spatial pattern Communication innovation Neural network algorithm
• Palabras claves:Problema de grafo multietapa; Problema de camino más corto de origen único y destino único; Sistemas de computación de grafos distribuidos; DMGA; Características estructurales; Algoritmo de programación dinámica
• Keywords:Multistage graph problem; Single-source single-sink shortest path problem; Distributed graph computing systems; DMGA; Structural characteristics; Dynamic programming algorithm