{"id":7862,"date":"2019-01-21T02:50:30","date_gmt":"2019-01-21T01:50:30","guid":{"rendered":"http:\/\/www.sigterritoires.fr\/?p=7862"},"modified":"2019-01-21T09:50:41","modified_gmt":"2019-01-21T08:50:41","slug":"como-desarrollar-una-aplicacion-con-pgrouting-en-windows-3-el-algoritmo-dijkstra","status":"publish","type":"post","link":"https:\/\/www.sigterritoires.fr\/index.php\/es\/como-desarrollar-una-aplicacion-con-pgrouting-en-windows-3-el-algoritmo-dijkstra\/","title":{"rendered":"C\u00f3mo desarrollar una aplicaci\u00f3n con pgrouting en Windows (3): el algoritmo Dijkstra"},"content":{"rendered":"\n

El algoritmo de Dijkstra es un algoritmo<\/a>\npara la determinaci\u00f3n del camino m\u00e1s corto<\/a>, dado un v\u00e9rtice<\/a> origen, hacia el resto de los\nv\u00e9rtices en un gr\u00e1fico que tiene pesos en cada arista.Considera una gr\u00e1fica orientada, ponderada por los reales\npositivos y un v\u00e9rtice en el origen . Se refiere a la construcci\u00f3n gradual de una\nsub-gr\u00e1fica en la que est\u00e1n clasificados los diferentes v\u00e9rtices en orden creciente\nde su distancia m\u00ednima al v\u00e9rtice original. La distancia es la suma de los\npesos de los arcos considerados. <\/p>\n\n\n\n\n\n\n\n

La sintaxis del algoritmo de Dijkstra es la siguiente: <\/p>\n\n\n\n

pgr_dijkstrar<\/strong> (<\/strong> sql<\/strong> texto ,<\/strong> entero de origen<\/strong>\n,<\/strong> entero de destino<\/strong> , dirigido<\/strong> booleano );<\/strong> <\/p>\n\n\n\n

donde origen <\/em><\/strong>es el punto de partida deseado de la ruta , objetivo<\/em><\/strong>\nel punto final de la ruta y la cadena sql es de tipo: <\/p>\n\n\n\n

SELECCIONE ID, origen, destino, costo [,<\/strong> reverse_cost<\/strong> ] DESDE\nla<\/strong> red<\/strong> <\/p>\n\n\n\n

La variable booleana \u00a0\u00bb directed \u00bb permite la toma en consideraci\u00f3n\nlos caminos de un solo sentido. Por defecto ella es \u00a0\u00bb true \u00ab\u00a0.\n<\/p>\n\n\n\n

La orden devuelve un conjunto de elementos ( seq , path_seq [, start_vid\n] [, end_vid ], node, edge, cost, agg_cost ). A diferencia del algoritmo A *, donde\nse cuenta con un punto de partida y un punto final del itinerario, el algoritmo\nDijstra admite varios puntos de entrada y salida. <\/p>\n\n\n\n

En el conjunto de salida, seq<\/em><\/strong> es el n\u00famero secuencial del\nsegmento en el conjunto global, path_seq<\/em><\/strong> es el n\u00famero secuencial\ndel segmento en el itinerario , start_vid<\/em><\/strong> y end_vid<\/em><\/strong>\nson el punto de salida y llegada del itinerario y no son indicados a menos que\nexistan varias source <\/em><\/strong>o target <\/em><\/strong>en par\u00e1metro\ndel algoritmo , node<\/em><\/strong> y edge <\/em><\/strong>son los puntos inicial y final\ndel tramo. considerado , cost<\/em><\/strong> es el costo del tramo y agg_cost<\/em><\/strong>\nes el costo acumulado desde la salida del itinerario.<\/p>\n\n\n\n

Elecci\u00f3n<\/strong> del \u00ab\u00a0<\/strong> costo<\/strong> \u00a0\u00bb de un tramo<\/strong> .<\/strong> <\/p>\n\n\n\n

El algoritmo de caminos m\u00ednimos busca el camino con el menor coste\nposible. En funci\u00f3n de sus objetivos, deber\u00e1 decidir qu\u00e9 elemento de coste tomar\u00e1\nen consideraci\u00f3n. <\/p>\n\n\n\n

Retomemos nuestra base de datos OpensStreetMap . Usted tiene un campo\n\u00ab\u00a0cost\u00a0\u00bb que extrae la longitud de la secci\u00f3n en grados. Si usa este\ncampo en el algoritmo de Dijkstra como valor de costo, el itinerario propuesto\nser\u00e1 el camino m\u00e1s corto entre los dos puntos seleccionados . Veamos un ejemplo\n. <\/p>\n\n\n\n

La orden siguiente, calcula el itinerario entre los puntos 69072 y 64204\nutilizando el campo \u00ab\u00a0cost\u00a0\u00bb que corresponde a la longitud del tramo . \n\nSELECT seq , path_seq , node, edge,\ndi.cost , agg_cost , the_geom
\nFROM pgr_dijkstra (
\n‘SELECT gid como id, fuente, destino, costo, reverse_cost DE public.ways ‘,
\n69072, 64204, falso ) como di
\nJOIN a public.ways ways_vertices_pgr
\nON di.edge = ways_vertices_pgr.gid ; \n\n\n\n<\/p>\n\n\n\n