Calcular el camino más corto y la distancia entre varios pares de DO utilizando pgr_dijkstra one-to-one

Question

Mi objetivo es encontrar la distancia y el camino más corto entre más de 1000 pares Origen-Destino en una red de carreteras. Tengo una tabla con el ID del par, el ID del vértice de origen y el ID del vértice de destino para cada par. Todo funciona bien cuando uso el pgr_dijkstra, donde obtengo un camino y un agg_cost para el siguiente ejemplo:

SELECT * FROM pgr_dijkstra(
'SELECT gid as id, source, target, length as cost FROM route1',
48302, 44382, FALSE); 

Lo que me gustaría hacer es sustituir los vértices de origen y destino (48302, 44382) por las columnas de id de vértices de origen y destino de mi tabla, emparejadas por el ID del par. En otras palabras, me gustaría obtener la distancia y la ruta de todos mis pares de OD en una sola consulta.

Answer 1

¿se refiere a encontrar la ruta más corta desde todos los puntos a todos los demás puntos de su red?

Eso es posible con el Camino más corto de todos los pares, algoritmo de Floyd-Warshall pero en notación "O grande" es O(n^3) por lo que tardará mucho tiempo (10 nodos tardarán 1.000 unidades de tiempo, 100 nodos tardarán 1.000.000 de unidades de tiempo...)

También es posible que se quede sin memoria para más de unos pocos miles de puntos.

También hay una implementación de Algoritmo de Johnson que no he probado, que podría ser más rápido.

EDITAR releyendo tu pregunta, eso es probablemente excesivo si sólo quieres la ruta/distancia para un subconjunto de los nodos de tu red.