El algoritmo de par más corto disjunto de bordes es un algoritmo en el enrutamiento de redes informáticas . [1] El algoritmo se utiliza para generar el par más corto de rutas disjuntas de borde entre un par de vértices dado de la siguiente manera:
- Ejecute el algoritmo de ruta más corta para el par de vértices dado
- Reemplace cada borde de la ruta más corta (equivalente a dos arcos dirigidos de manera opuesta) por un solo arco dirigido hacia el vértice de la fuente
- Haz que la longitud de cada uno de los arcos anteriores sea negativa
- Ejecute el algoritmo de ruta más corta (Nota: el algoritmo debe aceptar costos negativos)
- Borre los bordes superpuestos de los dos caminos encontrados e invierta la dirección de los arcos restantes en el primer camino más corto de modo que cada arco en él se dirija ahora hacia el vértice del sumidero. Se obtiene el par de caminos deseado.
El algoritmo de Suurballe resuelve el mismo problema más rápidamente al volver a ponderar los bordes del gráfico para evitar costos negativos, lo que permite utilizar el algoritmo de Dijkstra para los dos pasos de ruta más cortos.
Algoritmo
G = (V, E) d (i) - la distancia del vértice i (i∈V) del vértice fuente A; es la suma de arcos en un camino posible desde el vértice A al vértice i. Tenga en cuenta que d (A) = 0; P (i): el predecesor del vértice I en el mismo camino. Z - el vértice de destino
Paso 1.
Comience con d (A) = 0,d (i) = l (Ai), si i∈ΓA; Γi ≡ conjunto de vértices vecinos del vértice i, l (ij) = longitud del arco desde el vértice i al vértice j. = ∞, de lo contrario (∞ es un número grande definido a continuación); Asigne S = V- {A}, donde V es el conjunto de vértices en el gráfico dado.Asigne P (i) = A, ∀i∈S.
Paso 2.
a) Encuentre j∈S tal que d (j) = min d (i), i∈S.b) Establezca S = S - {j}.c) Si j = Z (el vértice de destino), END; de lo contrario, vaya al paso 3.
Paso 3.
∀i∈Γj, si d (j) + l (ij)a) establezca d (i) = d (j) + l (ij), P (i) = j.b) S = S ∪ {i}Vaya al paso 2.