Algoritmo di Eppstein e algoritmo di Yen per k percorsi più corti

Question

Sto cercando di capire esattamente come funzionano questi algoritmi, ma non sono riuscito a trovare una spiegazione semplice. Apprezzerei molto se qualcuno potesse fornire o indicarmi una descrizione di questi algoritmi che è più facile da capire rispetto alla descrizione nei documenti originali. Grazie.

Answer 1

Prima di tutto lascia che ti fornisca i link ai documenti di cui stavi parlando. carta

di Eppstein: D. Eppstein, “Finding the k shortest paths,” SIAM J. Comput., vol. 28, no. 2, pp.652–673, Feb. 1999

carta di Yen: J. Y. Yen, “Finding the K Shortest Loopless Paths in a Network,” Management Science, vol. 17, no. 11, pp. 712–716, 1971.

Ecco la mia spiegazione dell'algoritmo di Yen:

algoritmo di Yen utilizza due liste, vale a dire la lista A (percorsi più brevi permanente dalla sorgente alla destinazione - ordinati cronologicamente) e lista B (tentativi/percorsi candidati più brevi). Per prima cosa devi trovare il 1 ° percorso più breve dalla sorgente alla destinazione usando un algoritmo con il percorso più breve adatto (ad esempio Dijkstra). Quindi Yen sfrutta l'idea che i cammini più brevi di k-es possono condividere bordi e sotto-percorsi (percorso dalla sorgente a qualsiasi nodo intermedio all'interno della rotta) da (k-1) -th percorso più breve. Quindi devi prendere (k-1) il percorso più breve e rendere a turno ogni nodo nella rotta irraggiungibile, cioè rimuovere il bordo particolare che va al nodo all'interno della rotta. Una volta che il nodo è irraggiungibile, trova il percorso più breve dal nodo precedente alla destinazione. Quindi si ha una nuova rotta che viene creata aggiungendo il percorso secondario comune (dall'origine al nodo precedente del nodo irraggiungibile) e aggiunge il nuovo percorso più breve dal nodo precedente alla destinazione. Questo percorso viene quindi aggiunto all'elenco B, a condizione che non sia mai apparso nell'elenco A o nell'elenco B prima. Dopo averlo ripetuto per tutti i nodi del percorso, devi trovare il percorso più breve nell'elenco B e spostarlo nell'elenco A. Devi solo ripetere questo processo per il numero di K che hai.

Questo algoritmo ha una complessità computazionale di O (kn^3). Si prega di leggere la carta per maggiori dettagli.

L'algoritmo è il seguente:

G = Adjacent Matrix of the Network 
Initialize: 
A_1 = shortest-path from source to destination 
Glocal ← Local copy of G 
for k = 2 → K do 
for i = 1 → [len(A_(k−1)) − 1] do 
    Current Node ← A_(k−1) [i] 
    Ri ← Sub-path (root) from source till current node in A_(k−1) 
    for j = 1 → k − 1 do 
    Rj ← Sub-path (root) from source till current node in A_j 
    if Ri == Rj then 
    Next Node ← Aj [i+1] 
    Glocal(Current Node, Next Node) ← infinity 
    Current Node ← unreachable 
    end if 
    end for 
    Si ← Shortest-path from current node till destination 
    Bi ← Ri + Si 
end for 
A_k ← Shortest-path amongst all paths in B 
Restore original graph: Glocal ← Local copy of G 
end for 

Purtroppo, non ho usato la propria Eppstein come algoritmo di Yen era ottimale per il mio problema.

Spero che questo aiuti. Saluti.

=====

Edit:

prega di dare un'occhiata al wikipedia entry pure. Ha un bell'esempio.

=====

Edit:

ho trovato alcune implementazioni in C. I collegamenti sono i seguenti:

Eppstein implementation e Loading Graph for Eppstein.

Se siete interessati, c'è un lazy version di Eppstein.Il link è il seguente:

Lazy Eppstein by Jimenez and Marzal

=====

Edit:

Solo un altro link. Questo contiene diverse implementazioni (C/C++).

=====

Edit:

ho trovato un good explanation dell'algoritmo di Eppstein.