El algoritmo de Dijkstra es un algoritmo para la determinación del camino más corto, dado un vértice origen, hacia el resto de los vértices en un gráfico que tiene pesos en cada arista.Considera una gráfica orientada, ponderada por los reales positivos y un vértice en el origen . Se refiere a la construcción gradual de una sub-gráfica en la que están clasificados los diferentes vértices en orden creciente de su distancia mínima al vértice original. La distancia es la suma de los pesos de los arcos considerados.
La sintaxis del algoritmo de Dijkstra es la siguiente:
pgr_dijkstrar ( sql texto , entero de origen , entero de destino , dirigido booleano );
donde origen es el punto de partida deseado de la ruta , objetivo el punto final de la ruta y la cadena sql es de tipo:
SELECCIONE ID, origen, destino, costo [, reverse_cost ] DESDE la red
La variable booleana » directed » permite la toma en consideración los caminos de un solo sentido. Por defecto ella es » true «.
La orden devuelve un conjunto de elementos ( seq , path_seq [, start_vid ] [, end_vid ], node, edge, cost, agg_cost ). A diferencia del algoritmo A *, donde se cuenta con un punto de partida y un punto final del itinerario, el algoritmo Dijstra admite varios puntos de entrada y salida.
En el conjunto de salida, seq es el número secuencial del segmento en el conjunto global, path_seq es el número secuencial del segmento en el itinerario , start_vid y end_vid son el punto de salida y llegada del itinerario y no son indicados a menos que existan varias source o target en parámetro del algoritmo , node y edge son los puntos inicial y final del tramo. considerado , cost es el costo del tramo y agg_cost es el costo acumulado desde la salida del itinerario.
Elección del « costo » de un tramo .
El algoritmo de caminos mínimos busca el camino con el menor coste posible. En función de sus objetivos, deberá decidir qué elemento de coste tomará en consideración.
Retomemos nuestra base de datos OpensStreetMap . Usted tiene un campo «cost» que extrae la longitud de la sección en grados. Si usa este campo en el algoritmo de Dijkstra como valor de costo, el itinerario propuesto será el camino más corto entre los dos puntos seleccionados . Veamos un ejemplo .
La orden siguiente, calcula el itinerario entre los puntos 69072 y 64204
utilizando el campo «cost» que corresponde a la longitud del tramo .
SELECT seq , path_seq , node, edge,
di.cost , agg_cost , the_geom
FROM pgr_dijkstra (
‘SELECT gid como id, fuente, destino, costo, reverse_cost DE public.ways ‘,
69072, 64204, falso ) como di
JOIN a public.ways ways_vertices_pgr
ON di.edge = ways_vertices_pgr.gid ;
El resultado , una vez cargado en QGis es el mismo que para el algoritmo A *
Problemas
Comparando con el algoritmo A *, advertirá que hay menos necesidad de poner en forma de la tabla de la capa red. Por otro lado, si usa los campos cost_s y reverse_cost_s , recibirá los mismos mensajes de error si hay valores cero. Vea el artículo anterior ( Expandir una aplicación con pgrouting con Windows (2): el algoritmo A * ) para resolver estos problemas. En este artículo utilizamos la versión 2.2.3 de pgrouting . Si usa versiones anteriores podrá encontrar un problema de tipo de campo source y objetivo de su base de datos:
En efecto , si el número de nodos en su red es muy importante, los campos source y objetivo pueden ser de tipo bigint . Las versiones anteriores de pgRouting no tomaban en consideración este tipo de entero .
Compruebe su versión con la consulta SQL
SELECt pgr_version ();
Itinerarios múltiples
Aquí hay un ejemplo de un cálculo de itinerario con tres puntos de partida y un punto de llegada :
SELECT seq , path_seq , start_vid , node, edge, di.cost ,
agg_cost , the_geom
FROM pgr_dijkstra (
‘SELECT gid como id, fuente, destino, costo_s costo, reverse_cost_s como
reverse_cost FROM public.ways ‘,
ARRAY [69072,21576,62667] , 64204, verdadero ) como di
JOIN a public.ways ways_vertices_pgr
ON di.edge = ways_vertices_pgr.gid ;
Esta consulta calcula los itinerarios entre los
puntos de partida. 69072, 21576 y 62667 y el punto de llegada 64204
Una vez cargado en QGis, el resultado es el siguiente
Variante pgr_dijkstraCost
Usted dispone de una variante del algoritmo Dijkstra en la que usted indica el punto de partida y el punto de llegada y a cambio, simplemente, obtiene el costo total del trayecto .
Aquí hay un ejemplo con el itinerario entre los puntos 69072 y 64204.
SELECT * FROM pgr_dijkstraCost (
‘SELECT gid como id, fuente, destino, costo_s costo, reverse_cost_s como
reverse_cost FROM public.ways ‘,
69072, 64204);
