Portada	Favoritos
Lista Articulos: [0-C] [C-I] [I-P] [P-Z] | Todas las categorías | Página aleatoria | Lo que enlaza aquí

Algoritmo de Dijkstra

También llamado algoritmo de caminos mínimos, es un algoritmo para la determinación del camino más corto que une dos vértices en un grafo dirigido y etiquetado. Su nombre se refiere a Edsger Dijkstra, su desarrollador.

La idea subyacente en este algoritmo consiste en ir explorando todos los caminos más cortos que parten del vértice de origen y que llevan a todos los demás vértices; cuando se obtiene el camino más corto que lleva al vértice de destino, se detiene el algoritmo.

Descripción detallada

• Sea G=(V,A) un grafo dirigido y etiquetado.
• Sean los vértices a ∈ V y z ∈ V; a es el vértice de origen y z el vértice de destino.
• Sea un conjunto C ⊂ V, que contiene los vértices de V cuyo camino más corto desde a todavía no se conoce.
• Sea un vector D, con tantas dimensiones como elementos tiene V, y que “guarda” las distancias entre a y cada uno de los vértices de V.
• Sea, finalmente, otro vector, P, con las mismas dimensiones que D, y que conserva la información sobre qué vértice precede a cada uno de los vértices en el camino.

El algoritmo para determinar el camino de longitud mínima entre los vértices a y z es:

1. C ← V
2. Para todo vértice i ∈ C, i ≠ a, se establece D_i ← ∞ ; D_a ← 0
3. Para todo vértice i ∈ C se establece P_i = a
4. Se obtiene el vértice s ∈ C tal que no existe otro vértice w ∈ C tal que D_w < D_s
   • Si s = z entonces se ha terminado el algoritmo.
5. Se elimina de C el vértice s: C ← C−{s}
6. Para cada arista e ∈ A de longitud l, que une el vértice s con algún otro vértice t ∈ C,
   • Si l+D_s < D_t, entonces:
     1. Se establece D_t ← l+D_s
     2. Se establece P_t ← s
7. Se regresa al paso 4

Al terminar este algoritmo, en D_z estará guardada la distancia mínima entre a y z. Por otro lado, mediante el vector P se puede obtener el camino mínimo: en P_z estará y, el vértice que precede a z en el camino mínimo; en P_y estará el que precede a y, y así sucesivamente, hasta llegar a a.