1. Definición y Propósito: Describir qué es el algoritmo de Dijkstra y su objetivo en la búsqueda de caminos más cortos en un grafo ponderado. Explicar la importancia de este algoritmo en el campo de la teoría de grafos.
El algoritmo de Dijkstra es un algoritmo que tiene como finalidad “encontrar la ruta más corta o el camino más corto entre los nodos de un grafo. Específicamente, puedes encontrar el camino más corto desde un nodo (llamado el nodo de origen) a todos los otros nodos del grafo, generando un árbol del camino más corto”(Estefania Cassingena Navone, 2022).
Su objetivo es encontrar el camino más corto entre un nodo origen y cualquier otro nodo que sería el nodo de destino, el camino más corto en un grafo ponderado es aquel que tenga el menor peso en la suma de las aristas desde el nodo origen y el nodo destino
La relevancia del algoritmo de Dijkstra reside en que cumple una función fundamental, que es “determinar el camino más corto para ejecutar desde un vértice origen hasta el resto de los vértices ubicados en un grafo con pesos en cada arista” (TFG online, 2023).
Con esto dicho, el algoritmo cumple con múltiples casos, como ejemplo tenemos la característica que el algoritmo funciona para grafos dirigidos y no dirigidos no importando la dirección que pueda tener el grafo ponderado, esto lo vuelve especialmente útil no solo en el ámbito teórico, sino que se puede aplicar a problemas reales como redes de transporte o el flujo de datos en redes computacionales.
Por ello el algoritmo es un pilar en la teoría de grafos, ya que gracias a la característica de identificar el camino más corto entre un nodo a hasta un nodo b, lo convierte en una base para el desarrollo de algoritmos más avanzados en la teoría de grafos.
2. Funcionamiento del Algoritmo: Investigar y explicar cómo funciona el algoritmo de Dijkstra. Incluir una descripción de los pasos que se siguen, desde la inicialización hasta la actualización de distancias. Se sugiere realizar un ejemplo paso a paso con un grafo simple.
Con el algoritmo de Dijkstra, se puede encontrar la ruta más corta o el camino más corto entre los nodos de un grafo. Específicamente, se puede encontrar el camino más corto desde un nodo (llamado el nodo de origen) a todos los otros nodos del grafo, generando un árbol del camino más corto.
Aspectos básicos del algoritmo de Dijkstra
- El algoritmo de Dijkstra esencialmente comienza en el nodo que se elija (el nodo inicial) y examina el grafo para identificar la ruta más corta entre ese nodo y todos los demás nodos en el grafo.
- El algoritmo mantiene un registro de la distancia más corta conocida desde el nodo inicial hasta cada nodo y actualiza el valor si encuentra una ruta más corta.
- Una vez que el algoritmo ha identificado la ruta más corta entre el nodo inicial y otro nodo, ese nodo se marca como “visitado” y se añade a la ruta.
- El proceso continúa hasta que todos los nodos en el grafo han sido incorporados a la ruta. De esta manera, tenemos un camino que conecta el nodo inicial con todos los otros nodos siguiendo la ruta más corta posible para llegar a cada uno de ellos.
Condiciones
- La distancia desde el nodo de origen a sí mismo es 0. En este ejemplo, el nodo de origen será el nodo 0, pero puede ser cualquier nodo que se elija.
- La distancia desde el nodo de origen a todos los otros nodos del grafo no se ha calculado todavía, así que utilizaremos el símbolo de infinito para representar esto al iniciar el algoritmo.
Dado que hemos decidido comenzar en el nodo 0, podemos
marcar este nodo como explorado. Lo eliminamos de la lista de nodos pendientes
de visitar y añadimos un borde rojo al nodo correspondiente en el diagrama:
Ahora debemos empezar a comprobar la distancia desde el nodo 0 hasta sus nodos vecinos. Como puedes observar, estos nodos son el nodo 1 y el nodo 2 (conectados por los arcos rojos en el diagrama):
Necesitamos actualizar las distancias desde el nodo 0 hasta el nodo 1 y el nodo 2 con los valores de los arcos que los conectan con el nodo 0 (el nodo inicial).
Estos valores son, respectivamente:
- Seleccionar el nodo más cercano al nodo inicial según las distancias conocidas hasta el momento.
- Marcarlo como explorado.
- Añadirlo a la ruta.
Lo señalamos con un cuadrado rojo en la lista para indicar que ha sido “explorado” y que ya hemos determinado la ruta más corta hasta este nodo:
Lo tachamos en rojo de la lista de nodos pendientes de visitar:
Ahora tenemos que analizar los nuevos nodos adyacentes para encontrar el camino más corto para llegar a ellos. Solo analizaremos los nodos que son adyacentes a los nodos que ya son parte del camino más corto (el camino marcado con arcos rojos).
Los nodos 3 y 2 son adyacentes a los nodos que ya están en el camino porque están directamente conectados al nodo 1 y al nodo 0, respectivamente (como puedes ver en el siguiente diagrama). Estos son los nodos que analizaremos en el próximo paso.
Ahora que hemos calculado las distancias a los nodos vecinos, debemos elegir el nodo que se añadirá a la ruta más corta. Debemos seleccionar el nodo pendiente de visitar con la distancia más corta (conocida hasta ahora) hasta el nodo inicial.
A
partir de la lista de distancias, podemos identificar rápidamente que este nodo
es el nodo 2, con una distancia de 6:
Lo añadimos a la ruta de manera gráfica con un borde rojo alrededor del nodo y un arco rojo:
También lo señalamos como explorado añadiendo un pequeño cuadrado rojo en la lista de distancias y lo eliminamos de la lista de nodos pendientes de visitar.
