Este es un algoritmo del campo de teoría de grafos. Para el que no sepa qué es la teoría de grafos, es el campo de las matemáticas y de la computación que estudia los grafos (increíble pero cierto), pero ¿qué es un grafo?

Un grafo, por ejemplo, es lo que tenemos ahí arriba. Digámoslo así, es una especia de mapa formado por dos objetos, los vértices, y las aristas. Haciendo una analogía con un mapa de un páis, podemos decir que las ciudades son los nodos, y las aristas son las carreteras.

Estas carreteras, tienen sus longitudes (aunque a veces hay problemas en los que la longitud de las aristas da igual, de hecho en el grafo de arriba no viene especificada), lo que en teoría de grafos se conoce como el peso de una arista.

Una vez que ya sabemos lo que es un grafo, podemos preguntarnos, ¿existe algún algoritmo para encontrar el camino más corto entre 2 vértices? Sí, existen multitud de algoritmos que sirven para eso y hoy os voy a hablar un poco sobre el Algoritmo de Dijkstra.

Este algoritmo calcula las distancias menores desde un vértice hasta el resto de vértices del grafo. Es considerado unos de los mejores algoritmos para hacer esto.

Aquí podrás ver como funciona:

El algoritmo de Disjktra (wikipedia)

En un artículo próximo escribiré mi implementación del algoritmo en python.