Algoritmo de Dijkstra

Valora este artículo

El algoritmo de Dijkstra, también llamado algoritmo del camino mínimo, desarrollado por el Informático Edsger Dijkstra en 1.959, determina el camino mas corto entre un nodo inicial y el resto de nodos de un grafo ponderado.

Algoritmo

Sea \(G\) un grafo ponderado de \(N\) nodos no aislados, sea \(x\) el nodo inicial y \(D\) el vector que guardará las distancias desde \(x\) al resto de nodos.

  1. Inicializar los valores de \(D\) a \(\infty\) excepto el que corresponde a la posición de \(x\) que se inicializará a \(0\).
  2. Sea \(a\) el nodo actual.
  3. Recorreremos los nodos no marcados adyacentes a \(a\), nodos \(v_i\).
  4. Calcularemos las distancias desde el nodo actual \(a\) a sus vecinos \(dt(v_i)=D_a+d(a,v_i)\). Si \(dt(v_i) \lt D_{v_i} \to D_{v_i} = dt(v_i)\).
  5. Se marca como completo el nodo \(a\).
  6. Seleccionamos el siguiente nodo actual aquel que tenga menor valor en \(D\) y volvemos al paso 3 mientras queden nodos sin marcar.

Complejidad

La complejidad del algoritmo es \(O(|N|^2)\).

 

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *