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);
