Tras ello, añadiremos la extensión de pgrouting así:

routing1=# create extension pgrouting;

Comprobamos la versión de pgrouting instalada con el commando pgr_version().

routing1=# select pgr_version();

                   pgr_version
-------------------------------------------------
 (2.1.0,pgrouting-2.1.0,1,b38118a,master,1.59.0)

Caminos más cortos

El camino más corto[1] consiste en el cálculo de la ruta entre dos puntos (nodos) de forma que la suma de los costes de los tramos constituyentes es minimizada. El coste de un tramo puede consistir en su longitud, el tiempo en atravesarlo o cualquier otra variable.

Pgrouting implementa varios algoritmos diferentes para resolver el problema del camino más corto entre dos puntos o ejes de una red lineal.

• Algoritmo de Dijkstra[2] (comando pgr_dijkstra de pgrouting). Este algoritmo devuelve el camino más corto (de todos los posibles) entre dos nodos de una red. Para ello, no se necesita conocer las coordenadas de los puntos de los nodos de la red sino simplemente disponer de la numeración de los puntos inicial y final de cada tramo así como su longitud. Pgrouting incluye también otra variedad llamada Bi-directional Dijkstra (comando pgr_bdDijkstra de pgrouting) que realiza dos rutas óptimas: una desde el origen al destino y otra del destino al origen, y se detiene cuando alcanza el punto medio de las dos rutas.

Otra variedad de este algoritmo es el K-Shortest Path (comando pgr_ksp de pgrouting). Este algoritmo permite obtener no solo el camino más óptimo sino los n caminos más optimos.

• Algoritmo Astar (comando pgr_astar de pgrouting). Además de los números de los nodos inicial y final de cada tramo y su longitud utiliza para los cálculos las coordenadas X e Y de dichos nodos. Mediante un algoritmo heurístico es capaz de encontrar un camino que tiene una alta probabilidad de ser uno de los más cortos entre dos nodos de la red. Al contrario que el algoritmo de Dijkstra es capaz de trabajar con redes grandes. Al igual que en Dijkstra también se implementa la variedad bidireccional de este algoritmo (comando pgr_bdAstar de pgrouting).
• Algoritmo Turn Restriction Shortest Path (comando pgr_trsp de pgrouting). Es un algoritmo que necesita también las coordenadas como el Astar pero añade la posibilidad de añadir restricciones a la red, por ejemplo, giros no permitidos.

Además tenemos otros dos algoritmo: All Pairs Shortest Path, Johnson’s Algorithm y All Pairs Shortest Path, Floyd-Warshall Algorithm (comandos pgr_apspJohnson y pgr_apspWarshall) de pgrouting) que obtienen los caminos más óptimos entre todos los pares de nodos del grafo