17 septiembre, 2013
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.