Dijkstra es un algoritmo de búsqueda de ruta más corta desarrollado por Edsger Dijkstra en 1956 y es utilizado para encontrar la ruta más corta entre dos nodos en un grafo con pesos en las aristas. El algoritmo utiliza una estrategia de "visto y vencido", en la que se marcan los nodos ya visitados y se actualiza la distancia más corta desde el nodo de inicio a cada nodo del grafo. Es utilizado en una variedad de aplicaciones, como la planificación de rutas en sistemas de navegación y redes de telecomunicaciones.
Con el algoritmo de Dijkstra vamos a lograr encontrar el costo mínimo de recorrer desde un nodo en particular a todos los nodos que pertenecen al grafo.
Se puede aplicar tanto en grafos dirigidos como en no dirigidos. Otra condición es que los valores de las aristas sean todos positivos.
Existen distintas formas de anotar los resultados que vamos obteniendo, acá voy a trabajar un sistema en forma de “etiquetas” las cuales funcionan de la siguiente manera:
Dentro de corchete y separados por un punto y coma anotamos:
Por fuera del corchete y entre paréntesis anotamos
Ejemplo de etiqueta:
A medida que vayamos resolviendo un ejercicio vamos a ir obteniendo más de una etiqueta para un mismo nodo. Si la etiqueta que añadimos tiene un peso mayor a la que ya estaba, entonces la tachamos, en caso contrario, tachamos la que ya estaba antes (a veces en lugar de tachar le pongo una X al lado, para que la raya no tape los números y quede más prolijo). De esta manera vamos a ir quedando con muchas etiqueta tachadas y una sola que corresponde a la de menor peso, esta es la que nos interesa.