O algoritmo de Dijkstra

Cando nos enfrontamos a problemas de optimización, a intuición enseguida nos di que atopar a mellor solución posible -mellor, no sentido de máis barata, máis curta ou máis rápida- adoita ser unha tarefa titánica, debido ao colosal tamaño de opcións que implican. Abonda con pensar en exemplos coma o coñecido problema do viaxeiro: o número de rutas posibles medra de maneira explosiva, até facerse inabordable mesmo para os ordenadores máis potentes. Neste contexto, resulta especialmente interesante o algoritmo de Dijkstra, que aborda con eficiencia un problema que, a priori, semella complexo: atopar o camiño máis curto entre dous puntos nunha rede.

Nestes escenarios, non é raro renunciar á perfección e conformarse con solucións “abondo boas”, obtidas de forma rápida mediante heurísticas ou regras prácticas. Neste marco aparecen os chamados algoritmos voraces (greedy), que toman decisións locais -a mellor opción en cada paso- coa esperanza de acadar unha solución global óptima. Porén, esta estratexia ten os seus riscos: os algoritmos voraces son rápidos e elegantes, mais non sempre garanten o mellor resultado, nin sequera un bo.

A modo de exemplo, pense vostede que un algoritmo voraz para chegar ao cumio dunha montaña podería consistir en atopar primeiro a pendente máis pronunciada na súa posición actual e, a continuación, dar un paso nesa dirección. Repetir este procedemento a cada momento levará finalmente a un punto no que en todas as direccións hai que descender. Nese intre está vostede no cumio dun outeiro… pero non necesariamente é o outeiro máis alto. Isto explícase porque é posible que a ruta até o cumio do pequeno outeiro que acaba de escalar comezase con máis pendente que a ruta que leva á montaña máis alta, polo que inicialmente seguiu un camiño equivocado por culpa de certa “miopía heurística”.

Con todo, hai problemas nos que esta filosofía non só funciona, senón que o fai de maneira sorprendentemente eficaz. No problema do camiño máis curto nunha rede, como a que modela un sistema de estradas, o número de rutas posibles entre dous puntos pode ser descomunal. Pero, por fortuna, contamos co enxeño dos matemáticos e científicos informáticos que abordaron o problema e actualmente dispoñemos de estratexias como a proposta en 1959 por Edsger Wybe Dijkstra (1930 – 2002). Grazas a ela, é posible atopar o camiño óptimo de forma eficiente en tempo polinómico (do problema P versus NP falaremos outro día), algo fundamental en aplicacións coma os sistemas de navegación ou para encamiñar o tráfico en Internet.

Aquí e agora imos tratar de desentrañar como funciona o algoritmo de Dijkstra, por que é un exemplo paradigmático de método voraz que si acada a solución óptima e que ideas matemáticas se agochan detrás da súa aparente simplicidade.

O algoritmo de Dijkstra comeza nun vértice inicial e, en cada iteración, engade outro vértice á árbore dos camiños máis curtos. Este novo vértice é o punto máis próximo á raíz que aínda está fóra da árbore. Déixolle a ligazón a unha animación na que poderá visualizar o proceso. Teña en conta que non importa o número de arestas no camiño da árbore, senón a suma dos seus pesos. No exemplo da animación, o peso de cada aresta é igual á súa lonxitude visible.

Como xa temos falado de grafos, a vostede xa non lle dará medo que lle presente un grafo coma o da figura 1. É simple, é escasamente realista, pero ten poucos datos e así resulta manexable, de tal forma que se entenda ben en que consiste o procedemento. Se quere, podemos imaxinar un contexto, algo do estilo A: casa, B: instituto, C: biblioteca pública, D: pavillón deportivo, E: estación de autobuses.

En cada aresta do grafo recóllese o seu peso: a distancia en quilómetros entre eses lugares. O obxectivo é atopar o camiño máis curto dende a casa (A) até calquera dos outros lugares da súa vila. O algoritmo funciona así:

• Comézase nun vértice inicial (A).

• Vanse asignando as distancias mínimas coñecidas.

• En cada paso, escóllese o vértice non visitado máis próximo.

• Actualízanse as distancias dos seus veciños.

Paso 0: situación inicial

Comezamos no vértice A; loxicamente, a distancia até o propio A é 0. Do resto de distancias non sabemos nada, así que as poñemos “infinitas”.

Vértice	Distancia dende o vértice A
A	0
B	∞
C	∞
D	∞
E	∞

Paso 1: saímos de A

Dende A podemos ir a B (6 km) ou a C (3 km). Actualizamos as distancias.

Vértice	Distancia dende o vértice A
A	0
B	6
C	3
D	∞
E	∞

Escollemos o vértice non visitado que teña menor distancia: é C. Iso significa que xa sabemos con seguridade que o camiño máis curto dende A até C mide 3 km.

Paso 2: revisamos os veciños de C

Dende C podemos ir a B (2 km), a D (3 km) ou a E (7 km). Como dende A a C había 3 km, agora temos novas distancias medidas dende A:

• De A a B: 3 + 2 = 5 km

• De A a D: 3 + 3 = 6 km

• De A a E: 3 + 7 = 10 km

Comparando coas distancias recollidas no paso 1, actualizamos a táboa para todos os vértices que agora teñan unha distancia menor.

Vértice	Distancia dende o vértice A
A	0
B	5
C	3
D	6
E	10

Escollemos o vértice non visitado que teña menor distancia: é B. Por tanto, tamén sabemos xa que o camiño máis curto dende A até B mide 5 km.

Paso 3: revisamos os veciños de B

Dende B podemos ir a D (5 km). Tamén se pode ir a C, pero para ese vértice xa coñecemos a distancia máis curta, así que neste paso xa o descartamos. Como sabemos que a distancia mínima de A a B é de 5 km, agora temos unha nova distancia medida dende A:

• De A a D: 5 + 5 = 10 km

Comparando coas distancias recollidas na táboa no paso anterior comprobamos que non se consegue ningunha mellora, polo que neste paso non cómpre actualizar a táboa.

Escollemos o vértice non visitado que teña menor distancia: é D. Queda fixada a distancia máis curta a el dende A: é de 6 km.

Paso 4: revisamos os veciños de D

Dende D podemos ir, de entre os vértices non visitados aínda, a E (2 km). Como sabemos que a distancia mínima de A a D é de 6 km, agora temos unha nova distancia medida dende A:

• De A a E: 6 + 2 = 8 km

Comparando coa táboa anterior, vemos unha distancia mellorada, polo que a actualizamos.

Vértice	Distancia dende o vértice A
A	0
B	5
C	3
D	6
E	8

O único vértice non visitado que queda é o E. Como neste intre queda fixada a súa distancia mínima, o proceso remataou, posto que xa cumprimos o obxectivo para todos os vértices. E non só sabemos as distancias óptimas, senón tamén o percorrido polo que se obteñen. É interesante remarcar que o camiño máis directo non ten por que ser o máis curto (fíxese: de A a B pode ir directo, pero chega antes pasando por C), algo do que vostede xa será consciente se adoita usar o Google Maps. É moi probable que, cando utilice a aplicación, esta empregue algunha variación do algoritmo de Dijkstra para poñerse a calcular números en segredo, a partir dos cales decide que lle ruta suxerirlle.

A → C → B: 5 km

A → C: 3 km

A → C → D: 6 km

A → C → D → E: 8 km

Así, o algoritmo de Dijkstra avanza de forma moi ordenada; dalgún xeito, é un proceso fermoso. Primeiro fixa o que ten máis preto e logo usa esa información para mellorar o resto. A partir de aí só é cuestión de repetir o proceso. Coma se fose ampliando círculos arredor do punto de partida: primeiro alcanza o máis próximo, despois o seguinte e así sucesivamente.

A clave está en que, cando o algoritmo fixa un vértice, esa distancia xa é definitiva. Non aparecerá máis adiante un camiño mellor. Por iso o método é tan potente: evita probar todas as rutas posibles, que serían moitísimas (incluso no noso exemplo, tan simple el, serían bastantes), e aínda así garante a solución óptima.

Algunhas referencias:

• Dijkstra, Edsger Wybe (1959). “A note on two problems in connexion with graphs”, Numerische Mathematik, 1, pp. 269 – 271.

• Grima, Clara (2021). En busca del grafo perdido. Matemáticas con puntos y rayas. Editorial Planeta, Barcelona.

• Yates, Kit (2019). The maths of life and death. Why maths is (almost) everything. Quercus Editions, Londres.