Ruta más corta en ausencia del borde dado

Question

Supongamos que se nos da un gráfico ponderado G (V, E).

El gráfico contiene N vértices (numeradas de 0 a N-1) y M bidireccional bordes.

Cada borde (vi, vj) tiene distancia postive d (es decir, la distancia entre los dos vértices vivj es d)

Hay atmost un borde entre dos cualesquiera vértice y también hay no auto bucle (ie.no borde conectar un vértice a sí mismo.)

también se nos da S el vértice fuente y D el vértice de destino.

vamos Q sea el número de consultas, cada una de las consultas contiene un borde e (x, y).

Para cada consulta, tenemos que encontrar la ruta más corta desde la fuente S hasta el destino D, suponiendo que el borde (x, y) está ausente en el gráfico original. Si no existe ninguna ruta de S a D, entonces tenemos que imprimir Nº

Las restricciones son de alta < 0 = (N, Q, M) < = 25000

¿Cómo resolver este problema de manera eficiente?

Hasta ahora lo que hice está implementado el algoritmo simple Dijakstra.

para cada consulta Q, cada vez que estoy asignación (x, y) al infinito y encontrar Dijakstra camino más corto.

Pero este enfoque será muy lento, ya que la complejidad global será Q (complejidad del tiempo de la trayectoria Dijastra Shortes) *

Ejemplo ::

N=6,M=9 
S=0 ,D=5 

(u,v,cost(u,v)) 
0 2 4 
3 5 8 
3 4 1 
2 3 1 
0 1 1 
4 5 1 
2 4 5 
1 2 1 
1 3 3 

Total Queries =6 

Query edge=(0,1) Answer=7 
Query edge=(0,2) Answer=5 
Query edge=(1,3) Answer=5 
Query edge=(2,3) Answer=6 
Query edge=(4,5) Answer=11 
Query edge=(3,4) Answer=8 

Answer 1

Primero, calcule el árbol de ruta más corta desde el nodo de origen hasta el destino.

En segundo lugar, recorra todas las consultas y corte la ruta más corta en el borde especificado por la consulta; esto define un problema de corte mínimo, donde se tiene la distancia entre el nodo fuente y la frontera de una partición y la frontera de la otra y el destino; puede calcular este problema muy fácilmente, a lo sumo O(|E|). Por lo tanto, este algoritmo requiere O(Q|E| + |V|log|V|), asintóticamente más rápido que la solución ingenua cuando |V|log|V| > |E|.

Esta solución reutiliza el cálculo de Dijkstra, pero aún procesa cada consulta individualmente, por lo que quizás haya margen para mejoras explotando el trabajo realizado en una consulta anterior en consultas sucesivas al observar la forma del corte inducido por el borde.

Answer 2

Una optimización sencilla: en primer lugar ejecutar el Dijkstra gráfico completo (sin bordes eliminados).

Luego, para cada consulta, verifique si el borde solicitado pertenece a esa ruta más corta. Si no, eliminar este borde no hará ninguna diferencia.

Answer 3

Para cada consulta, el gráfico cambia muy poco, por lo que puede reutilizar gran parte de su cálculo.

que sugieren el siguiente enfoque:

1. calculan la ruta más corta desde S a todos los demás nodos (Dijkstras algoritmo hace por usted ya). Esto le dará un árbol de ruta más corta T.
2. Para cada consulta, tome este árbol, podado por el borde (x, y) de la consulta. Este podría ser el árbol original (si (x, y) no estaba en el árbol) o un árbol más pequeño T '.
   • Si D está en el T ', se puede tomar el camino más corto original,
   • De lo contrario iniciar Dijkstra, pero el uso de las etiquetas que ya tiene desde el T' (estos caminos son ya más pequeño) como etiquetas permanentes.

Si ejecuta el Dijkstra en el paso 2 se puede reutilizar el podado de una parte del árbol T de la siguiente manera: Cada vez que desee marcar un nodo permanente (que es uno de los nodos no en T ') puede adjuntar el subárbol completo de este nodo (desde el árbol original T) a su nuevo árbol de ruta más corta y etiquetar todos sus nodos como permanentes.

De esta manera reutiliza la mayor cantidad de información posible desde la primera ruta de acceso más corta.

---

En su ejemplo esto significaría:

Calcular ruta más corta del árbol: 0-> 1-> 2-> 3-> 4-> 5 (en este caso una muy simple)

Supongamos ahora que recibimos la consulta (1,2).

Podamos borde (1,2) que nos deja con 0-> 1

A partir de ahí empezamos Dijkstra conseguir 2 y 3 nodos marcados como permanentes próximos. Conectamos 1 a 2 y de 1 a 3 en el nuevo árbol de camino más corto y una el subárbol de edad de 3: 2 < -0-> 1-> 3-> 4-> 5

así que conseguimos el más corto camino con solo ejecutar un paso adicional del Algoritmo de Dijkstras.

---

La corrección del algoritmo Del conjunto de caminos en el árbol T siendo como máximo, siempre que en el nuevo gráfico de la consulta (en el que cada camino más corto sólo puede ser más largo). Por lo tanto, podemos reutilizar cada ruta desde el árbol que todavía es factible (es decir, donde no se eliminó borde).

Si el rendimiento importa mucho, puede mejorar el rendimiento de Dijkstra mediante una gran cantidad de trucos de implementación. Un buen punto de entrada para esto podría ser el DIMACS Shortest Path Implementation Challenge.