ds.algorithms – Paralelización de Dijkstra

Pregunta:

Me gustaría saber cuál es el mejor método para paralelizar el algoritmo de Dijkstra.

Gracias.

Respuesta:

Hay un algoritmo paralelo para las rutas más cortas del Ph.D. de 1977 de Carla Savage. tesis que consiste en formar una matriz cuadrada con 0 en las entradas diagonales, la longitud de las aristas en las entradas fuera de la diagonal correspondientes a las aristas, y un número suficientemente grande para las restantes entradas fuera de la diagonal, y luego cuadrar repetidamente esta matriz en el (min, +) álgebra .

Después de los pasos de cuadratura de $ \ lceil \ log_2 n \ rceil $, los números en la matriz resultante son las distancias entre cada par de vértices. Cada paso de cuadratura es fácil de paralelizar con tiempo logarítmico y trabajo cúbico. Entonces, en general, este algoritmo toma $ O (\ log ^ 2 n) $ tiempo y $ O (n ^ 3 \ log n) $ trabajo. Con un poco de cuidado (usando un álgebra un poco más complicada), esto se puede modificar para que también proporcione el primer paso de cada camino más corto en el mismo tiempo y límites de trabajo.

Sin embargo, si solo desea las rutas más cortas de una sola fuente en lugar de todas las rutas más cortas de los pares, no conozco nada que se acerque al trabajo total del algoritmo secuencial de Dijkstra y que proporcione mucho en el camino de una aceleración paralela.

Leave a Comment

Your email address will not be published.

Scroll to Top

istanbul avukat

-

web tasarım