Percorso minimo in assenza del bordo specificato

Question

Supponiamo di ricevere un grafico ponderato G (V, E).

Il grafico contiene N vertici (numerate da 0 a N-1) e M bidirezionale bordi.

Ogni bordo (vi, vj) ha postive distanza d (cioè la distanza tra i due vertici vivj è d)

C'è atmost un bordo tra due qualsiasi vertice e c'è anche alcun sé anello (ie.no bordo collegare un vertice a stessa.)

Inoltre c'è dato S vertice sorgente e D il vertice di destinazione.

let Q sia il numero di query, ciascuna query contiene un bordo e (x, y).

Per ogni query, dobbiamo trovare il percorso più breve da dall'origine S alla destinazione D, assumendo che il bordo (x, y) sia assente nel grafico originale. Se non esiste alcun percorso da S a D, allora dobbiamo stampare No.

I vincoli sono alta 0 < = (N, A, M) < = 25000

Come risolvere questo problema in modo efficiente?

Fino ad ora quello che ho fatto è implementato il semplice algoritmo di Dijakstra.

per ogni query Q, ogni volta che io sono assegnazione (x, y) per Infinity e trovare Dijakstra percorso più breve.

Ma questo approccio sarà molto lento come complessità generale sarà Q (tempo di complessità del percorso Dijastra Shortes) *

Esempio ::

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

Prima di tutto, calcolare l'albero del percorso più breve dal nodo di origine alla destinazione.

In secondo luogo, eseguire il ciclo su tutte le query e tagliare il percorso più breve sul bordo specificato dalla query; questo definisce un problema min-cut, in cui si ha la distanza tra il nodo sorgente e la frontiera di una partizione e la frontiera dell'altro e della destinazione; puoi calcolare questo problema molto facilmente, al massimo O(|E|).

Pertanto, questo algoritmo richiede O(Q|E| + |V|log|V|), asintoticamente più veloce della soluzione naif quando |V|log|V| > |E|.

Questa soluzione riutilizza il calcolo di Dijkstra, ma elabora comunque ogni query singolarmente, quindi forse c'è spazio per miglioramenti sfruttando il lavoro svolto in una query precedente nelle query successive osservando la forma del taglio indotto dal bordo.

Answer 2

Una semplice ottimizzazione: prima esecuzione Dijkstra su grafico completo (senza bordi rimossi).

Quindi, per ogni query, verificare se il bordo richiesto appartiene a quel percorso più breve. In caso contrario, la rimozione di questo bordo non farà alcuna differenza.

Answer 3

Per ogni query il grafico cambia solo leggermente, quindi è possibile riutilizzare molti calcoli.

suggerisco il seguente approccio:

1. Calcola il percorso più breve da S a tutti gli altri nodi (Dijkstra Algoritmo fa per voi già). Questo ti darà un albero del percorso più breve T.
2. Per ogni query, prendere questo albero, potato dal bordo (x, y) dalla query. Questo potrebbe essere l'albero originale (se (x, y) non era dove sull'albero) o un albero più piccolo T '.
   • Se D è nel T ', si può prendere il percorso più breve originale
   • In caso contrario avviare Dijkstra, ma utilizzare le etichette già presenti dalla T' (questi percorsi sono già più piccolo) come etichette permanenti.

Se si esegue il Dijkstra al punto 2 è possibile riutilizzare la potatura di una parte di albero T nel modo seguente: Ogni volta che si desidera contrassegnare un nodo permanente (che è uno dei nodi non in T ') è possibile collegare l'intero sottoalbero di questo nodo (dall'albero originale T) al nuovo albero del percorso più breve e etichettare tutti i suoi nodi permanenti.

In questo modo si riutilizza quante più informazioni possibili dal primo percorso percorso più breve.

---

Nel tuo esempio questo significherebbe:

Calcola percorso più breve albero: 0-> 1-> 2-> 3-> 4-> 5 (in questo caso un molto semplice)

Supponiamo ora di ottenere una query (1,2).

potiamo bordo (1,2) lasciandoci con 0-> 1

Da lì si parte Dijkstra ottenendo 2 e 3 come prossimi nodi contrassegnati permanenti. Colleghiamo 1-2 e 1-3 nel nuovo percorso più breve albero e allegare il vecchio sottoalbero da 3: 2 < -0-> 1-> 3-> 4-> 5

Così abbiamo ottenuto la più breve percorso con appena eseguito un ulteriore passaggio dell'algoritmo Dijkstras.

---

La correttezza dell'algoritmo Dall'insieme tutti i percorsi in tree T essendo al massimo il tempo che nel nuovo grafico dalla query (dove ogni percorso più breve non può che essere più lungo). Quindi riusciamo a riutilizzare ogni percorso dall'albero che è ancora fattibile (cioè dove non è stato rimosso alcun bordo).

Se le prestazioni sono importanti, è possibile migliorare le prestazioni di Dijkstra attraverso numerosi trucchi di implementazione. Un buon punto di ingresso per questo potrebbe essere il DIMACS Shortest Path Implementation Challenge.