El algoritmo de Dijkstra es un algoritmo de caminos mínimos. Está diseñado para encontrar el camino de menor ponderación (sea peso, distancia, coste, …) entre un nodo y todos los demás. Sin embargo, para poder explicar el Algoritmo de Dijkstra (y concretamente esta implementación en PHP) debería empezar con un poco de teoría de grafos. El problema es que entonces el artículo se alargaría muchísimo, así que sólo daré una breve pincelada, pero entraré en materia de inmediato.
Un grafo es una representación basada en vértices (nodos) y aristas (conexiones). Para entenderlo mejor, un grafo podría ser la representación de aeropuertos y los vuelos entre ellos. Cada vértice sería un aeropuerto, y un vuelo sería una arista, con lo que si hay varios vuelos, también hay varias aristas. Veamos un ejemplo de grafo:
Este grafo sería un «grafo dirigido», dado que las aristas tienen una dirección; van de un vértice a otro. El peso de cada arista podría ser la distancia en millas, y el número dentro de cada vértice podría ser el código de un aeropuerto.
El algoritmo de Dijkstra, como decía al principio, calcula el camino mínimo desde un vértice a todos los demás. No sólo eso; puede indicar además por qué nodos pasar. Esto lo hace gracias a dos arrays en los que guarda la ponderación más baja (el menor peso, distancia o coste de las conexiones) y el camino a seguir. Y atención, sólo calcula el camino mínimo; no calcula los ‘n’ caminos mínimos entre dos vértices.
Para entender el algoritmo de Dijkstra recomiendo una lectura a la Wikipedia. En pocas palabras, el objetivo del algoritmo es ir encontrando paulatinamente los caminos más cortos desde el vértice de origen. El algoritmo se puede optimizar enormemente si en cada iteración busca primero los vértices vecinos de menor peso. Esto es algo que podemos conseguir con el uso de una cola de prioridad.
Cabe destacar, además, que el algoritmo de Dijkstra no funciona en grafos con aristas negativas. Dado que siempre busca el camino con menor ponderación, podría darse el caso de que en iteraciones posteriores el coste general de un determinado camino disminuyera, lo que llevaría a caminos mínimos falsos basados en ciclos negativos.
He implementado el algoritmo de Dijkstra en PHP y está disponible en mi repositorio de Github. Eres libre de usarlo en tus proyectos. 😉
Además, en esta implementación del Algoritmo de Dijkstra en PHP hago dos cosas que considero interesantes:
- Uso la Cola de Prioridad en PHP que publiqué hace unos días. Como digo, esto mejora enormemente su rendimiento en grafos grandes. Ver análisis de coste en el repositorio.
- Propongo una manera de devolver la información muy interesante para proyectos que requieran del uso del algoritmo de Dijkstra. Se trata de un array bien estructurado que es muy fácil de leer.
¿Te ha gustado este algoritmo? Entonces te estaré muy agradecido si me compras un café. 😉
