Paso Más Corto desde un Inicio Único

Para el problema de la ruta corta tenemos varios algoritmos, en esta oportunidad se explicará el algoritmo de dijkstra el cual usa una técnica voraz (greedy).

Descripción

El algoritmo de dijkstra determina la ruta más corta desde un nodo origen hacia los demás nodos para ello es requerido como entrada un grafo cuyas aristas posean pesos. Algunas consideraciones:

• Si los pesos de mis aristas son de valor 1, entonces bastará con usar el algoritmo de BFS(algoritmo de búsqueda: Breadth First Search).
• Si los pesos de mis aristas son negativos no puedo usar el algoritmo de dijsktra, para pesos negativos tenemos otro algoritmo llamado Algoritmo de Bellmand-Ford.

Como trabaja

Primero marcamos todos los vértices como no utilizados. El algoritmo parte de un vértice origen que será ingresado, a partir de ese vértices evaluaremos sus adyacentes, como dijkstra usa una técnica greedy – La técnica greedy utiliza el principio de que para que un camino sea optimo, todos los caminos que contiene también deben ser óptimos- entre todos los vértices adyacentes, buscamos el que esté más cerca de nuestro punto origen, lo tomamos como punto intermedio y vemos si podemos llegar más rápido a través de este vértice a los demás. Después escogemos al siguiente más cercano (con las distancias ya actualizadas) y repetimos el proceso. Esto lo hacemos hasta que el vértice no utilizado más cercano sea nuestro destino. Al proceso de actualizar las distancias tomando como punto intermedio al nuevo vértice se le conoce como relajación (relaxation).

Dijkstra es muy similar a BFS, si recordamos BFS usaba una Cola para el recorrido para el caso de Dijkstra usaremos una Cola de Prioridad o Heap, este Heap debe tener la propiedad de Min-Heap es decir cada vez que extraiga un elemento del Heap me debe devolver el de menor valor, en nuestro caso dicho valor será el peso acumulado en los nodos.

Tanto java como C++ cuentan con una cola de prioridad ambos implementan un Binary Heap aunque con un Fibonacci Heap la complejidad de dijkstra se reduce haciéndolo más eficiente, pero en un concurso más vale usar la librería que intentar programar una nueva estructura como un Fibonacci Heap, claro que particularmente uno puede investigar y programarlo para saber cómo funciona internamente.

Algoritmo en pseudocódigo

Considerar distancia[ i ] como la distancia más corta del vértice origen ingresado al vértice i.

Luces de Árbol de Costo Mínimo

Este problema surge de la necesidad de encontrar dentro de un grafo no dirigido, un árbol que recorra todos los nodos del grafo, y cuya suma de los pesos o valores de las aristas sea menor entre todos los arboles que se puedan formar en el grafo en cuestión.

El árbol resultante es el llamado Árbol de cobertura mínima. Ejemplo, podemos encontrar dentro del grafo, el árbol de cobertura mínima, puesto que observamos que al número de arboles que se pueden generar es significativo. 

Algoritmo de Prim

El algoritmo de Prim es un algoritmo perteneciente a la teoría de los grafos para encontrar un árbol de cobertura mínimo dentro de un grafo no dirigido. En otras palabras, el algoritmo encuentra un subconjunto de aristas que forman un árbol con todos los vértices, donde el peso total de todas las aristas en el árbol es el mínimo posible. Ejercicio:

Primero elegimos un nodo que tomara la función de nodo raíz y lo señalamos.

Luego se encuentran las aristas que estén conectadas al nodo raíz.

De las aristas encontradas se procede a determinar cual es la que tiene menor peso y se la señala.

En el caso de encontrarse con aristas que tengan el mismo peso se procede a seleccionar una de ellas de forma aleatoria.

Se procede a marcar el nodo al cual se encuentra conectada la arista anteriormente seleccionada.

Luego se vuelve a comparar los pesos entre los nodos relacionados, en este caso A-C, como los pesos son iguales son iguales se puede escoger cualquier arista.

Se vuelve a marcar el nodo que resultó estar conectada a la arista y se repite de forma continua los mismos pasos hasta tener un árbol que una todos los vértices.

Finalmente podemos observar que todos los nodos están unidos, es decir el árbol de cobertura mínimo para el nodo raíz A, está dado por la siguiente figura:

Algoritmo de Kruskal

De igual forma el algoritmo de kruskal es un algoritmo de la teoría de grafos, que es utilizado para encontrar el árbol de cobertura mínimo dentro de un grafo determinado.

Es decir, busca un subconjunto de aristas que, formado un árbol, incluyen todos los vértices y donde el valor total de todas las aristas del árbol es el mínimo. Ejercicio:

Se tiene un grafo inicial del cual partimos:

Primero procedemos a determinar de entre todos los nodos las aristas cuál es la arista que tiene el menor peso y la seleccionamos.

Procedemos a señalar la arista y los vértices que une tomando en cuenta lo explicado anteriormente.

Realizamos el mismo procedimiento, encontramos el valor menor de los pesos y marcamos los vértices que una dicha arista. 

Podemos observar que el siguiente valor de arista a tomar debe ser el número 3, pero en ese caso estaríamos generando un recorrido cerrado así que tomamos el siguiente valor que en este caso será el 4.

Si podemos observar, se vuelve a generar el inconveniente anterior así que elegimos el valor que le sigue.

En el caso de que el valor que le siga se repita, se puede escoger cualquiera de las dos aristas, tomando en cuenta que no se debe generar un lazo cerrado.

En la gráfica se puede observar que las dos aristas coinciden en un punto, pero es necesario aclarar que no se genera un lazo cerrado ya que solo son trayectorias que están pasando por un lugar en común más no están en ningún momento en intersección.

El árbol expandido que se genera es el siguiente:

La aplicación de estos problemas de optimización dentro de nuestra especialidad y nuestro diario vivir se ubica en las redes de comunicación eléctrica, telefónica, carretera, ferrovía, aérea, marítima, etc., donde los nodos representan puntos d consumo eléctrico, teléfonos, aeropuertos, computadoras, y las aristas podrían ser de alta tensión, cable de fibra óptica, rutas aéreas, etc.