Algoritmo de Dijkstra – Notas leídas

Algoritmo de Dijkstra. También llamado algoritmo de caminos mínimos, es un algoritmo para determinar el camino más corto dado un origen de vértice al resto de los vértices de un gráfico con pesos en cada borde. Su nombre se refiere a Edsger Dijkstra , quien lo describió por primera vez en 1959 .

Resumen

[ hide ]

  • 1 aplicaciones
  • 2 Características del algoritmo
  • 3 pasos del algoritmo
  • 4 Ejecutando el algoritmo
  • 5 Fin del proceso de ejecución
  • 6 Pseudocódigo
    • 1 cola de prioridad
    • 2 Sin cola de prioridad
  • 7 Enlaces externos

Aplicaciones

En varias aplicaciones donde se aplican gráficos, es necesario conocer la ruta más barata entre dos vértices dados:

  • Distribución de productos a una red de establecimientos comerciales.
  • Distribución de correo postal.
  • Sea G = (V, A) una gráfica dirigida ponderada.

El problema con la ruta más corta de vértice a vértice es encontrar la ruta más barata de vértice a vértice v. El costo de una ruta es la suma de los costos (pesos) de los arcos que la componen.

Características del algoritmo

  • Es un algoritmo codicioso.
  • Trabaje por etapas y tome la mejor solución en cada paso del camino sin considerar las consecuencias futuras.
  • El óptimo encontrado en un paso se puede cambiar más tarde si surge una mejor solución.

Pasos del algoritmo

Algoritmo 24.1: algoritmo de Dijkstra. Inicialización.

  • Sea V un conjunto de vértices de una gráfica.
  • Sea C una matriz de costos de los bordes del gráfico, donde en C [u, v] el costo del borde se almacena entre uy v.
  • Sea S un conjunto que contendrá los vértices para los que ya se ha determinado la ruta mínima.
  • Sea D una matriz unidimensional tal que D [v] es el costo de la ruta mínima desde el vértice original al vértice v.
  • Sea P una matriz unidimensional tal que P [v] es el vértice predecesor de v en la ruta mínima que hemos construido.
  • O la cumbre de origen vinítico. Recuerda que el algoritmo de Dijkstra determina las trayectorias mínimas que existen desde un vértice original hasta el resto de vértices.

Etapa 1. S ← {vinicial} // Inicialmente S contendrá el vértice // origen

2do paso. Para cada v∈V, v ≠ vinicial, haz

2.1. D [v] VS [vinicial, v] // Inicialmente, el costo de la // ruta av vinicial mínima es lo que está contenido en la // matriz de costos

2.2. PAG [v] ← vinicial // Inicialmente, // el predecesor de v en la ruta mínima construida // hasta ahora es vinicial

Paso 3. Siempre que (V – S ≠ ∅) lo haga // Siempre que haya vértices para // para los que no se ha determinado la ruta mínima

3.1. Elija un vértice w∈ (VS) tal que D [w] es el mínimo.

3.2. S ← S ∪ {w} // Agregamos w al conjunto S, ya que ya tenemos // la ruta mínima hacia w

3.3. Para cada v∈ (VS) haz

3.3.1. D [v] mente [v], D [w] + C [w, v]) // Usted elige entre // la ruta mínima a v que tiene // hasta ahora, y la ruta a v // que pasa por w por su ruta mínima // más barata.

3.3.2. Si min (D [v], D [w] + C [w, v]) = D [w] + C [w, v] luego P [v] ← w // Si elige w, entonces // el predecesor de v en este momento es w

Paso 4. Fin

Ejecutando el algoritmo

  • Paso 1: inicialización
  • Paso 2: elige un vértice w V – {A} tal que D [w] es mínimo, y agregue w al conjunto de soluciones S
  • Paso 3: cada v {C, D, E} hacer D [v] mente [v], D [w] + C [w, v])
  • Paso 4: elige un vértice w V – {A, B} tal que D [w] es mínimo, y agregue w al conjunto de soluciones S.
  • Paso 5: para cada v {C, E} hacer D [v] mente [v], D [w] + C [w, v]

Archivo: Something09.JPG

  • Paso 6: elige un vértice w V – {A, B, D} tal que D [w] es mínimo, y agregue w al conjunto de soluciones S.
  • Paso 7: para cada v {E} hacer D [v] mente [v], D [w] + C [w, v]
  • Paso 8: elige un vértice w V – {A, B, D, C} tal que D [w] es mínimo, y agregue w al conjunto de soluciones S.

Fin del proceso de ejecución

Después del paso 8 tenemos la siguiente situación:

  • El conjunto de vértices V = {A, B, C, D, E}
  • El conjunto de vértices para los que ya se ha determinado la ruta mínima S = {A, B, D, C, E}

Por tanto, como VS = Ø, el algoritmo finaliza, ya que para cada nodo del gráfico se ha determinado su camino mínimo. Tras la ejecución del algoritmo, tenemos:

D [B] D [C] D [D] D [E] PAG [B] PAG [C] PAG [D] PAG [E]

10 50 30 60 ADAC

Al final de la ejecución del algoritmo de Dijkstra, los costos de las rutas mínimas que parten del vértice original al resto de los vértices se almacenan en la tabla D. Por lo tanto, en nuestro ejemplo, la ruta mínima de A a B cuesta 10 , la ruta mínima de A a C cuesta 50, la ruta mínima de A a D cuesta 30 y la ruta mínima de A a E cuesta 60 ..

Veamos cómo se pueden obtener las rutas mínimas de la tabla de predecesores. Los caminos se reconstruyen desde la cumbre de destino hasta llegar a la cumbre original.

Ruta mínima (A, B) = AB desde P [B] = Uno

Ruta mínima (A, C) = ADC de P [C] = D y P [D] = Uno

Ruta mínima (A, D) = AD desde P [D] = Uno

Ruta mínima (A, E) = ADCE de P [E] = C, P [C] = D y P [D] = Uno

Finalmente, la ruta mínima que incluye todos los vértices del gráfico es ADCE.

Pseudocódigo

Cola de prioridad

DIJKSTRA (Gráfico G, source_node s)

para u V [G] hacer

distancia [u] = INFINITO

padre [u] = NULO

distancia [s] = 0

agregar (cola, (s, distancia [s]))

siempre que la cola no esté vacía, haz

u = extract_minimum (cola)

para toda la adyacencia [u] hacer

hasta ahora [v]> lejanía [u] + peso (u, v) hacer

distancia [v] = distancia [u] + peso (u, v)

padre [v] = tu

agregar (cola, (v, distancia [v]))

Sin cola de prioridad

Función Dijkstra (Gráfico G, node_output s)

// Usaremos un vector para registrar las distancias entre el nodo de salida y toda la distancia restante [n]

// Inicializa el vector con las distancias booleanas iniciales vistas [n]

// vector de boleanos para controlar los vértices para los que ya tenemos la distancia mínima

para cada w V [G] hacer

Si (no hay borde entre s y w) entonces

distancia [w] = Infinito // puedes marcar la casilla con un -1 por ejemplo

De lo contrario

distancia [w] = peso (s, w)

Fin si

final para

distancia [s] = 0

visto [s] = verdadero

// n es el número de vértices del gráfico

mientras (not_look_all_doing) hacer

vertex = take_the_minimum_of_vector distancia y no se muestra;

visto [vertex] = verdadero;

para cada w sucesores (G, vértice) hacer

hasta ahora [w]> lejanía [vertex] + peso (vértice, w) luego

distancia [w] = distancia [vertex] + peso (arriba, w)

Fin si

final para

terminar mientras

función final

Deja un comentario