{"id":1355,"date":"2013-09-17T16:28:52","date_gmt":"2013-09-17T14:28:52","guid":{"rendered":"http:\/\/www.human-computer.net\/blog\/?p=1355"},"modified":"2013-09-17T16:28:52","modified_gmt":"2013-09-17T14:28:52","slug":"optimizacion-del-algoritmo-del-camino-mas-corto-entre-todos-los-nodos-de-un-grafo-no-dirigido","status":"publish","type":"post","link":"https:\/\/yusef.es\/blog\/2013\/09\/optimizacion-del-algoritmo-del-camino-mas-corto-entre-todos-los-nodos-de-un-grafo-no-dirigido\/","title":{"rendered":"Optimizaci\u00f3n del algoritmo del camino m\u00e1s corto entre todos los nodos de un grafo no dirigido"},"content":{"rendered":"

Aviso<\/strong>: Entrada m\u00e1s t\u00e9cnica de lo normal<\/p>\n

Una forma muy habitual de estructurar datos es la de grafo, es decir, en forma de un conjunto de nodos y de enlaces entre los mismos. Los grafos no dirigidos son aquellos en los que entre dos nodos no puede existir m\u00e1s de un enlace y siempre bidireccional.<\/p>\n

El problema del camino m\u00e1s corto consiste en determinar cu\u00e1l es la distancia m\u00e1s peque\u00f1a que hay que recorrer para llegar de un nodo a otro. Se entiende que el valor asociado a los enlaces (su peso) representa distancias o disimilitudes. Si lo que tenemos es un grafo en el que los pesos indican proximidades o similitudes, siempre podemos transformarlos mediante la funci\u00f3n: disimilitud=1\/similitud.<\/p>\n

Floyd-Warshall<\/h3>\n

Uno de los algoritmos m\u00e1s utilizados para resolver este problema, seguramente por la belleza y simplicidad de su implementaci\u00f3n, es el de Floyd-Warshall<\/a>:<\/p>\n

\nfor k from 1 to |V|\n   for i from 1 to |V|\n      for j from 1 to |V|\n         if dist[i][k] + dist[k][j] < dist[i][j] then\n            dist[i][j] \u2190 dist[i][k] + dist[k][j]\n\n<\/pre>\n
Aunque en el caso de grafos no dirigidos se puede optimizar (dado que la matriz de enlaces es sim\u00e9trica), del pseudoc\u00f3digo se puede deducir su alta complejidad computacional, de orden exponencial.<\/p>\n
Esta complejidad es independiente de la densidad de enlaces. Ya que lo normal es que no tratemos con grafos con alta densidad (muchos nodos est\u00e1n enlazados a muchos nodos), sino de m\u00e1s baja densidad (pocos nodos est\u00e1n conectados a muchos nodos, y muchos nodos est\u00e1n conectados a pocos nodos), resultar\u00e1 m\u00e1s eficiente utilizar un enfoque diferente.<\/p>\n
Dijkstra<\/h3>\n
El algoritmo de Dijkstra<\/a>, dado un nodo s<\/em>, determina cu\u00e1l es el camino m\u00e1s corto desde ese nodo hacia el resto de nodos del grafo. Para calcular el camino m\u00e1s corto entre todos los nodos del grafo \u00fanicamente habr\u00eda que repetir el proceso por cada uno:<\/p>\n
\nfor each vertex s in Graph:<\/strong>\n      for each vertex v in Graph:                 \/\/ Initializations\n          dist[s][v]  := infinity;                \/\/ Unknown distance from s to v\n      end for                                                   \n      \n      dist[s][s] := 0;                            \/\/ Distance from s to s\n      Q := the set of all nodes in Graph;         \/\/ All nodes in the graph are\n                                                  \/\/ unoptimized \u2013 thus are in Q\n\n      while Q is not empty:                       \/\/ The main loop\n          u := vertex in Q with smallest distance in dist[s][];\n          remove u from Q;\n          if dist[s][u] = infinity:\n              break;                              \/\/ All remaining vertices are\n          end if                                  \/\/ inaccessible from source\n          \n          for each neighbor v of u:               \/\/ Where v has not yet been \n                                                  \/\/ removed from Q.\n              alt := dist[s][u] + dist_between(u, v);\n              if alt < dist[s][v]:                \/\/ Relax (u,v,a)\n                  dist[s][v]  := alt;\n                  decrease-key v in Q;            \/\/ Reorder v in the Queue\n              end if\n          end for\n      end while\nend for<\/strong>\n\n<\/pre>\n
C\u00f3digo adaptado de la wikipedia<\/a>.<\/p>\n
Ya que este es un algoritmo cuya complejidad computacional s\u00ed depende de la densidad de enlaces (siempre que la funci\u00f3n que devuelve los vecinos v<\/em> de u<\/em> est\u00e9 optimizada), en la gran mayor\u00eda de ocasiones resultar\u00e1 m\u00e1s eficiente que utilizar el algoritmo de Floyd-Warshall.<\/p>\n
Optimizaci\u00f3n<\/h3>\n
El algoritmo de Dijkstra se puede optimizar de diferentes formas, algunas comentadas en su entrada de la wikipedia. <\/p>\n
Una optimizaci\u00f3n que deduje conforme lo implementaba (y que imagino estar\u00e1 ya recogida en alg\u00fan trabajo) es la que se deriva de que su complejidad dependa precisamente de la densidad de enlaces.<\/p>\n
La idea consiste en eliminar o podar todos aquellos enlaces del grafo que no formen parte de ninguno de los caminos m\u00e1s cortos, para que as\u00ed el algoritmo no tenga que considerarlos en su b\u00fasqueda.<\/p>\n
Esta tarea de poda se puede acometer de dos formas. <\/p>\n
Procedimiento previo<\/strong> <\/p>\n
Identificar todas aquellas tripletas de nodos enlazados entre s\u00ed, y en cada tripleta eliminar de los tres enlaces que la forman, aquel cuya distancia sea mayor que la suma de las distancias de los otros dos.<\/p>\n
Procedimiento integrado<\/strong><\/p>\n
Aunque en las pruebas que he realizado este procedimiento parece menos eficiente que el anterior, otra opci\u00f3n es ir eliminando estos enlaces prescindibles como parte del procedimiento del algoritmo de Dijkstra: <\/p>\n
\n          for each neighbor v of u:                                                                                             \n              alt := dist[s][u] + dist_between(u, v) ;\n              if alt < dist[s][v]:                                  \n                  dist[s][v]  := alt ;\n                  decrease-key v in Q;                           \n\t          if s!=u and dist_between(s, v)>alt:\n\t     \t      remove-edge s,v from Graph;\n\t          end if<\/strong>\n              end if\n          end for\n\n<\/pre>\n
Es decir, si se encuentra una distancia entre dos nodos menor que la de su enlace directo, esto significa que dicho enlace es prescindible para los objetivos del algoritmo.<\/p>\n","protected":false},"excerpt":{"rendered":"
Aviso: Entrada m\u00e1s t\u00e9cnica de lo normal Una forma muy habitual de estructurar datos es la de grafo, es decir, en forma de un conjunto de nodos y de enlaces entre los mismos. Los grafos no dirigidos son aquellos en los que entre dos nodos no puede existir m\u00e1s de un enlace y siempre bidireccional. […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[9],"tags":[],"class_list":["post-1355","post","type-post","status-publish","format-standard","hentry","category-visualizacion-de-informacion"],"_links":{"self":[{"href":"https:\/\/yusef.es\/blog\/wp-json\/wp\/v2\/posts\/1355","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/yusef.es\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/yusef.es\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/yusef.es\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/yusef.es\/blog\/wp-json\/wp\/v2\/comments?post=1355"}],"version-history":[{"count":0,"href":"https:\/\/yusef.es\/blog\/wp-json\/wp\/v2\/posts\/1355\/revisions"}],"wp:attachment":[{"href":"https:\/\/yusef.es\/blog\/wp-json\/wp\/v2\/media?parent=1355"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/yusef.es\/blog\/wp-json\/wp\/v2\/categories?post=1355"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/yusef.es\/blog\/wp-json\/wp\/v2\/tags?post=1355"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}