DAA - Rutas más cortas
Algoritmo de Dijkstra
El algoritmo de Dijkstra resuelve el problema de las rutas más cortas de una sola fuente en un gráfico ponderado dirigido G = (V, E) , donde todos los bordes son no negativos (es decir, w (u, v) ≥ 0 para cada borde (u, v ) Є E ).
En el siguiente algoritmo, usaremos una función Extract-Min(), que extrae el nodo con la clave más pequeña.
Algorithm: Dijkstra’s-Algorithm (G, w, s)
for each vertex v Є G.V
v.d := ∞
v.∏ := NIL
s.d := 0
S := Ф
Q := G.V
while Q ≠ Ф
u := Extract-Min (Q)
S := S U {u}
for each vertex v Є G.adj[u]
if v.d > u.d + w(u, v)
v.d := u.d + w(u, v)
v.∏ := uAnálisis
La complejidad de este algoritmo depende completamente de la implementación de la función Extract-Min. Si la función de extracción mínima se implementa mediante búsqueda lineal, la complejidad de este algoritmo esO(V2 + E).
En este algoritmo, si usamos min-heap en el que Extract-Min() La función funciona para devolver el nodo desde Q con la clave más pequeña, la complejidad de este algoritmo se puede reducir aún más.
Ejemplo
Consideremos el vértice 1 y 9como vértice de inicio y de destino respectivamente. Inicialmente, todos los vértices excepto el vértice inicial están marcados con ∞ y el vértice inicial está marcado con0.
| Vértice | Inicial | Paso 1 V 1 | Paso 2 V 3 | Paso 3 V 2 | Paso 4 V 4 | Paso 5 V 5 | Paso 6 V 7 | Paso 7 V 8 | Paso 8 V 6 |
|---|---|---|---|---|---|---|---|---|---|
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 2 | ∞ | 5 | 4 | 4 | 4 | 4 | 4 | 4 | 4 |
| 3 | ∞ | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
| 4 | ∞ | ∞ | ∞ | 7 | 7 | 7 | 7 | 7 | 7 |
| 5 | ∞ | ∞ | ∞ | 11 | 9 | 9 | 9 | 9 | 9 |
| 6 | ∞ | ∞ | ∞ | ∞ | ∞ | 17 | 17 | dieciséis | dieciséis |
| 7 | ∞ | ∞ | 11 | 11 | 11 | 11 | 11 | 11 | 11 |
| 8 | ∞ | ∞ | ∞ | ∞ | ∞ | dieciséis | 13 | 13 | 13 |
| 9 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | 20 |
Por tanto, la distancia mínima del vértice 9 desde el vértice 1 es 20. Y el camino es
1 → 3 → 7 → 8 → 6 → 9
Esta ruta se determina en función de la información del predecesor.
Algoritmo Bellman Ford
Este algoritmo resuelve el problema de la ruta más corta de una sola fuente de un gráfico dirigido G = (V, E)en el que los pesos de los bordes pueden ser negativos. Además, este algoritmo se puede aplicar para encontrar el camino más corto, si no existe ningún ciclo ponderado negativo.
Algorithm: Bellman-Ford-Algorithm (G, w, s)
for each vertex v Є G.V
v.d := ∞
v.∏ := NIL
s.d := 0
for i = 1 to |G.V| - 1
for each edge (u, v) Є G.E
if v.d > u.d + w(u, v)
v.d := u.d +w(u, v)
v.∏ := u
for each edge (u, v) Є G.E
if v.d > u.d + w(u, v)
return FALSE
return TRUEAnálisis
El primero for El bucle se utiliza para la inicialización, que se ejecuta en O(V)veces. El siguientefor se ejecuta el bucle |V - 1| pasa sobre los bordes, lo que llevaO(E) veces.
Por tanto, el algoritmo de Bellman-Ford se ejecuta en O(V, E) hora.
Ejemplo
El siguiente ejemplo muestra cómo funciona el algoritmo Bellman-Ford paso a paso. Este gráfico tiene un borde negativo pero no tiene ningún ciclo negativo, por lo que el problema se puede resolver utilizando esta técnica.
En el momento de la inicialización, todos los vértices excepto la fuente están marcados con ∞ y la fuente está marcada con 0.
En el primer paso, todos los vértices que son accesibles desde la fuente se actualizan por costo mínimo. Por tanto, vérticesa y h se actualizan.
En el siguiente paso, vértices a, b, f y e se actualizan.
Siguiendo la misma lógica, en este paso los vértices b, f, c y g se actualizan.
Aquí vértices c y d se actualizan.
Por lo tanto, la distancia mínima entre vértices s y vértice d es 20.
Según la información del predecesor, la ruta es s → h → e → g → c → d