Algoritmo de Dijkstra en PHP

Posted by On Filed under Software, Tecnología
Algoritmo de Dijkstra en PHP

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:

Grafo de ejemplo para el algoritmo de Dijkstra en PHP

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.

Keep reading →

Cola de prioridad en PHP con cambio de prioridad

Posted by On Filed under Software, Tecnología

Hace ya unos días escribía un artículo sobre la Cola de Prioridad en PHP 7.4 que había implementado, y que está disponible en Github.

Por temas laborales he tenido que implementar el algoritmo de Dijkstra en PHP, y esto puede hacerse tanto con cola de prioridad como sin ella. La diferencia, en términos de coste de computación (Big O notation) era abismal, así que decidí usar la cola de prioridad al implementar Dijkstra. El problema era que mi cola de prioridad no tenía una función básica: «cambio de prioridad«.

Implementar ‘cambio de prioridad’ en la Cola de Prioridad en PHP

Después de analizar el código vi que era fácilmente implementable, testeable y usable en otros algoritmos, al estar debidamente encapsulada.

Keep reading →

Cola de prioridad en PHP 7.4

Posted by On Filed under Código limpio, Software, Tecnología, Testing 2 Comments

Hace unos días implementé una cola de prioridad en PHP 7.4 basándome en el concepto de ‘Heap‘. Un heap es un montón, una pila que parece desordenada, pero cuyo contenido sigue una lógica ordenada. De hecho, a partir de este concepto nace la técnica de ordenación del mismo nombre ‘Heap sort‘.

Antes de comentar la implementación de la cola, explicaré brevemente qué ventajas obtenemos al hacer así las cosas.

Ventajas de un heap para organizar una cola de prioridad

Al crear un sistema de prioridad como este buscamos obtener un medio ágil y rápido tanto de inserción como de extracción. En el caso del heap usamos un árbol binario, dado que con esta estructura podemos conseguir implementar la cola en un árbol (un array) homogéneo y completo. Este es el aspecto de un heap construido mediante un árbol binario:

Arbol binario que representa la cola de prioridad

Keep reading →