Algoritmo de Dijkstra: Ruta Óptima y Coste Mínimo

Clase 35 de 40 • Curso de Matemáticas Discretas

Clase anteriorSiguiente clase

Resumen

El algoritmo de Dijkstra va a buscar la ruta optima o de menor coste entre dos vértices.

Los pasos de este algoritmo son los siguientes:

  1.    Asignar el valor infinito a cada nodo que no ha sido visitado.

  2.    Mantener un registro de los nodos visitados.

  3.    Calcular la distancia a cada nuevo nodo sumando la distancia anterior.

  4.    Si la nueva distancia que se calculo es menor que la anterior entonces reemplazar en el nodo, sino dejar la anterior.

  5.    Se finalizará cuando se llega al nodo final.