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?