Algoritmo de Dijksta: el camino mínimo.Se da el caso en que se tiene un conjunto de nodos conectados entre sí, como quien tiene que recorrer una ciudad y los nodos representan los lugares a visitar en un día de turismo. Surge entonces la necesidad de averiguar cuál es el camino mínimo desde un nodo a cualquier otro nodo. Esto en matemáticas se puede modelar con grafos.
El algoritmo de Dijkstra, también llamado algoritmo de caminos mínimos, es un algoritmo para la determinación del camino más corto dado un vértice origen al resto de vértices en un grafo dirigido y con pesos en cada arista. Su nombre se refiere a Edsger Dijkstra, quien lo describió por primera vez en 1959.
La idea subyacente en este algoritmo consiste en ir explorando todos los caminos más cortos que parten del vértice origen y que llevan a todos los demás vértices; cuando se obtiene el camino más corto desde el vértice origen, al resto de vértices que componen el grafo, el algoritmo se detiene.
Vean este video en que enseñan a calcular las distancias mínimas:
Entradas
