Optimización del algoritmo del camino más corto entre todos los nodos de un grafo no dirigido

17 septiembre, 2013
Yusef Hassan

Aviso: Entrada más técnica 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ás de un enlace y siempre bidireccional.

El problema del camino más corto consiste en determinar cuál es la distancia más pequeña 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ón: disimilitud=1/similitud.

Floyd-Warshall

Uno de los algoritmos más utilizados para resolver este problema, seguramente por la belleza y simplicidad de su implementación, es el de Floyd-Warshall:

for k from 1 to |V|
   for i from 1 to |V|
      for j from 1 to |V|
         if dist[i][k] + dist[k][j] < dist[i][j] then
            dist[i][j] ← dist[i][k] + dist[k][j]

Aunque en el caso de grafos no dirigidos se puede optimizar (dado que la matriz de enlaces es simétrica), del pseudocódigo se puede deducir su alta complejidad computacional, de orden exponencial.

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án enlazados a muchos nodos), sino de más baja densidad (pocos nodos están conectados a muchos nodos, y muchos nodos están conectados a pocos nodos), resultará más eficiente utilizar un enfoque diferente.

Dijkstra

El algoritmo de Dijkstra, dado un nodo s, determina cuál es el camino más corto desde ese nodo hacia el resto de nodos del grafo. Para calcular el camino más corto entre todos los nodos del grafo únicamente habría que repetir el proceso por cada uno:

for each vertex s in Graph:
      for each vertex v in Graph:                 // Initializations
          dist[s][v]  := infinity;                // Unknown distance from s to v
      end for                                                   
      
      dist[s][s] := 0;                            // Distance from s to s
      Q := the set of all nodes in Graph;         // All nodes in the graph are
                                                  // unoptimized – thus are in Q

      while Q is not empty:                       // The main loop
          u := vertex in Q with smallest distance in dist[s][];
          remove u from Q;
          if dist[s][u] = infinity:
              break;                              // All remaining vertices are
          end if                                  // inaccessible from source
          
          for each neighbor v of u:               // Where v has not yet been 
                                                  // removed from Q.
              alt := dist[s][u] + dist_between(u, v);
              if alt < dist[s][v]:                // Relax (u,v,a)
                  dist[s][v]  := alt;
                  decrease-key v in Q;            // Reorder v in the Queue
              end if
          end for
      end while
end for

Código adaptado de la wikipedia.

Ya que este es un algoritmo cuya complejidad computacional sí depende de la densidad de enlaces (siempre que la función que devuelve los vecinos v de u esté optimizada), en la gran mayoría de ocasiones resultará más eficiente que utilizar el algoritmo de Floyd-Warshall.

Optimización

El algoritmo de Dijkstra se puede optimizar de diferentes formas, algunas comentadas en su entrada de la wikipedia.

Una optimización que deduje conforme lo implementaba (y que imagino estará ya recogida en algún trabajo) es la que se deriva de que su complejidad dependa precisamente de la densidad de enlaces.

La idea consiste en eliminar o podar todos aquellos enlaces del grafo que no formen parte de ninguno de los caminos más cortos, para que así el algoritmo no tenga que considerarlos en su búsqueda.

Esta tarea de poda se puede acometer de dos formas.

Procedimiento previo

Identificar todas aquellas tripletas de nodos enlazados entre sí, 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.

Procedimiento integrado

Aunque en las pruebas que he realizado este procedimiento parece menos eficiente que el anterior, otra opción es ir eliminando estos enlaces prescindibles como parte del procedimiento del algoritmo de Dijkstra:

          for each neighbor v of u:                                                                                             
              alt := dist[s][u] + dist_between(u, v) ;
              if alt < dist[s][v]:                                  
                  dist[s][v]  := alt ;
                  decrease-key v in Q;                           
	          if s!=u and dist_between(s, v)>alt:
	     	      remove-edge s,v from Graph;
	          end if
              end if
          end for

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.

¡Hola! Este blog se escribe con Calmly Writer y se gestiona con Wordpress (rss)