Esta historia continúa la de ayer a mediodía, así que más les conviene ir a verla ahora si no la han leído ya. Es un consejo de amigo.

Les había soltado un rollo sobre los grafos, y los algoritmos, y entre ellos mi favorito. Mi algoritmo favorito es el algoritmo de Dijkstra, que sirve para encontrar el camino más corto entre dos nodos; o sea, aquel en el que sumando los pesos de las aristas que hay que recorrer es el menor posible.

Una de las cosas más bonitas de este algoritmo es que para resolver este problema resuelve uno ligeramente distinto, que es (aparentemente) más complicado, pero que en realidad lleva exactamente el mismo tiempo: el algoritmo de Dijkstra, en realidad, calcula los caminos más cortos que unen un nodo “origen” con todos los demás nodos.

La idea tras el algoritmo es que disponemos de un conjunto de nodos de los que conocemos la longitud mínima del camino que los une con el nodo origen O (llamaremos a este conjunto “conjunto S”), y otro conjunto de nodos de los que conocemos la distancia de un camino que los une con O, pero este camino no tiene por qué ser mínimo (“conjunto N”).

En cada paso, del conjunto N escogeremos el nodo C, cuya distancia conocida es la menor del conjunto N; este nodo pasa ahora a formar parte de S, pues no es posible encontrar un camino que una O y C y sea más corto que el ya conocido; si lo hubiera pasaría sólo por nodos de S, y ya se habría descubierto antes.

Ahora, cada nodo que está directamente conectado con C tiene un camino que lo une con O pasando por C; si se calcula la longitud de este camino, podría descubrirse que ésta es menor que la longitud del camino más corto que se conocía para ese nodo antes de escoger C; si es así, habrá que actualizar la longitud conocida para el nodo. Tras las actualizaciones, se vuelve a escoger otro nodo C, repitiendo los pasos del algoritmo.

El algoritmo se termina cuando escogemos como nodo C el nodo que habíamos elegido como destino.

Explicado así, el algoritmo de Dijkstra no parece gran cosa, pero verlo hacer sobre papel es impresionante… Lástima que el formato de este weblog no se ajuste bien al tema. En la web que hay enlazada en el segundo párrafo hay una animación del algoritmo de Dijkstra en funcionamiento. Supongo que será buena, aunque no la he visto todavía… en este ordenador no tengo flash. Además, en esa página le explican el algoritmo en plan más informático, así que, a quien le interese…