Algoritmo dei cammini k più corti di Yen

1

Al momento sto cercando di capire l'algoritmo dei percorsi più brevi di Yen k. Mi sono basato sul documento originale e sull'articolo di Wikipedia, ma non riesco ancora a capire perché sia corretto se k > 2. In effetti, non vedo nemmeno perché funzioni sul seguente esempio:

Ad esempio, consideriamo i 3 percorsi più brevi da A a D. Questi sono A - > B - > C - > D (lunghezza 3), A - > B - > F - > D (lunghezza 4) e A - > B - > C - > E - > D (lunghezza 5). Da quello che ho capito dell'algoritmo, i 2 percorsi più brevi sono calcolati correttamente. Tuttavia, il 3o percorso più breve è una deviazione dal 2 ° percorso più breve al vertice B e il percorso A - > B è condiviso tra il 2 percorso più breve; di conseguenza, se ho capito bene l'algoritmo, non sarai in grado di passare B - > C che è l'unico modo per ottenere un terzo percorso più breve. Dalla mia comprensione, l'algoritmo sceglierà invece A - > B - > D (che è il quarto percorso più breve).

Cosa mi è mancato?

    
posta edouard.gilles 01.05.2016 - 18:16
fonte

1 risposta

0

Penso che ciò che ti confonde sia il pensiero che B si svuota alla fine di un'iterazione, dove per BI si intende il vettore del percorso da wikipedia pseudocodice .

Dopo la prima iterazione B ha i percorsi potenzialmente inferiori

B_vec == [A->B->F->D (length 4), A->B->C->E->D (length 5)]

Quando scegli il 2 ° percorso più breve, il percorso viene scoppiato, ma B_vec non viene svuotato prima della seconda iterazione che abbiamo

B_vec == [A->B->C->E->D (length 5)]

Dopo la seconda iterazione abbiamo

B_vec == [A->B->C->E->D (length 5), A->B->D (length 6)]

E A- > B- > C- > E- > D è selezionato

    
risposta data 02.05.2016 - 17:53
fonte

Leggi altre domande sui tag