Tengo un gráfico enorme que me gustaría procesar usando muchas máquinas.
Me gustaría calcular si el diámetro del gráfico es superior a 50.
¿Cómo dividiría los datos y escribiría un algoritmo paralelo que pueda calcularlos? (el valor de retorno es booleano)
El diámetro del gráfico es la mayor distancia entre cualquier par de vértices.
Respuestas
4 para la respuesta № 1La forma estándar de resolver esto sería un algoritmo de ruta más corta de todos los pares: el Algoritmo Floyd-Warshall Es un buen lugar para comenzar. Se encuentra otra opción usando Hadoop. aquí.
2 para la respuesta № 2
Echa un vistazo a Implementación paralela de algoritmos de diámetro gráfico.
También: Algoritmos de grafos paralelos