Otra de las secciones que abriré en mi blog será la del matemático del día. Cada vez que se cumpla una efeméride (normalmente, un aniversario o fallecimiento de algún matemático importante), hablaré de él en el blog. Para empezar, hoy toca hablar de Edsger Dijkstra, que tuvo importantes contribuciones en el mundo de la informática, y que hoy se cumple el décimo aniversario de su fallecimiento.

Edsger Wybe Dijkstra nació en Rotterdam, Holanda, en 1930 y falleció en Nuenen, Holanda, el 6 de agosto de 2002. Dijkstra estudió física teórica en la Universidad de Leiden, aunque más adelante descubrió que le interesaba más el mundo de la informática.

En 1952 empieza a trabajar en el Centro Matemático de Amsterdam, donde aumenta su curiosidad por la programación, aunque por aquel entonces no se reconocía el estudio de la programación. Después trabajó como investigador para Burroughs Corporation a principios de los 70, y en 1984 empezó a trabajar como investigador en la Universidad de Texas, en Austin, hasta el año 2000, cuando se retiró. Finalmente, fallece en Holanda en 2002 después de una larga lucha contra el cáncer.

Poco después de su muerte en el 2002, recibió la distinción ACM PODC Influential Paper Award en computación distribuida por su trabajo en la auto-estabilización en programas computacionales. Este premio fue renombrado a Premio Dijkstra el siguiente año en su honor.

Destacó, principalmente, por la notación polaca inversa, el algoritmo del banquero, la construcción del semáforo, importante en sistemas operativos para coordinar múltiples programas y procesadores, y el sistema operativo THE. También se le reconoce como autor de la expresión «Crisis del software«, que tuvo mucha trascendencia en la reunión de la OTAN de 1968.

Pero sobretodo, se le reconoce como el autor de la solución al problema del camino más corto, que se soluciona con el llamado algoritmo de Dijkstra.

A continuación pondré un ejemplo de lo que hace el algoritmo de Dijkstra, pero para los que no os queráis mirar el rollo que viene a continuación, os cuento: la idea consiste en intentar calcular la distancia más corta entre dos ciudades, teniendo un mapa de carreteras con diversas ciudades. Es decir, se trata de buscar los caminos más cortos posibles en una red de carreteras. Un problema que, a día de hoy, es bastante frecuente e interesante: siempre nos interesa saber cuál es la combinación de metros mejor para llegar a aquel restaurante, o qué autopista es mejor coger para ir de un sitio a otro, etc. Pues bien, Dijkstra encontró no sólo una manera de solucionarlo, sino que además lo consiguió de la manera más rápida posible.En el ejemplo siguiente, tenemos 7 ciudades, y queremos saber cuál es el camino más corto de 4 a 5. Se ve bastante rápidamente cuál es, pero lo haremos mediante el algoritmo de Dijkstra.

El algoritmo de Dijsktra hace lo siguiente:

1. En primer lugar, se considera que la distancia desde 4 a las demás ciudades es infinito.
2. Ahora, todos los nodos (ciudades) se irán etiquetando con dos cantidades: la distancia desde 4, y el último vértice visitado.
3. En el primer paso, miramos las distancias de 4 a los vértices vecinos y etiquetamos.
4. En este caso, el nodo 1 tendrá la etiqueta (3,4), ya que hay una arista que une 1 y 4 con distancia 3
5. El nodo 3 tendrá la etiqueta (2,4), porque la arista de 3 a 4 tiene distancia 2
6. El nodo 6 tendrá la etiqueta (1,4) ya que la arista de 4 a 6 tiene distancia 1
7. El nodo 7 tendrá la etiqueta (3,4). ya que la arista de 4 a 7 tiene distancia 3.
8. Ahora cogemos el nodo con la distancia más pequeña (el 6), y repetiremos el proceso.
9. El nodo 3 seguirá con la misma etiqueta, ya que el recorrido 4-6-3 tiene distancia 3, y el recorrido 4-3 tiene distancia 2.
10. El nodo 5 tendrá la etiqueta (4,6), ya que el recorrido 4-6-5 tiene distancia 1+3=4.
11. El nodo 7 seguirá con la misma etiqueta, ya que da lo mismo hacer 4-7 que 4-6-7
12. Repetimos el proceso con el nodo 3, que es el que tiene distancia más pequeña de los restantes.
13. Al nodo 2 le pondremos la etiqueta (3,3) ya que con el recorrido 4-3-2 hay una distancia 2+1=3
14. El nodo 5 no cambia de etiqueta, porque el recorrido 4-3-5 es más largo (dist. 5), que el recorrido 4-6-5 (dist.4)
15. Seguiríamos con los nodos 1,2,7,5, y comprobaríamos que las distancias no cambian.
16. Por lo tanto, la distancia de 4 a 5 es de 3, y se hace por el camino 4-6-5.

Parece complicado visto así, pero aunque pueda parecer lioso para 7 ciudades, la verdad es que cuando aparecen cientos de ciudades, el algoritmo de Dijkstra se muestra muy eficaz.

Referencias:

Biografía de Dijkstra en la Wikipedia

Explicación del algoritmo de Dijkstra en la Wikipedia

Ejemplo del algoritmo de Dijkstra por Ubicuos.com