Drumurile minime pana la $k-1$ sunt stocate compactate intr-un arbore de drumuri. Fiecarui nod din acel arbore ii corespunde un nod din graf, dar nu si invers, un nod din graf poate aparea de mai multe ori in arbore. Radacina arborelui corespunde nodului de start, iar toate frunzele arborelui corespund nodului de final, iar drumurile de la radacina catre frunze reprezinta fiecare cate un drum minim. Vezi in figura cum se compacteaza drumurile ({$1, 7, 4, 5$}), ({$1, 7, 3, 5$}), ({$1, 2, 4, 5$}) si ({$1, 2, 6, 4, 5$}). Drumurile sunt primele $4$ drumuri din graful desenat mai sus si luat drept exemplu.

!Al_K_lea_drum_minim?kshortest_graph.png!
!Al_K_lea_drum_minim?kshortest_tree.png!

!Al-K-lea-drum-minim?kshortest_graph.png!
!Al-K-lea-drum-minim?kshortest_tree.png!

Al {$k$}-lea drum minim trebuie sa corespund pana intr-un anumit punct cu un drum aflat deja in arbore, chiar daca punctul acela este de fapt nodul de start. Pentru a gasi urmatorul drum minim, incercam sa "deviem" din fiecare nod din arbore. Un drum de deviatie pentru un anume nod $X$ este un drum identic cu drumul de la radacina pana la nodul {$X$}, care apoi continua (deviaza) pe cel mai scurt drum pana la destinatie care nu a fost inca luat in cosiderare. Spre exemplu pentru nodul $4$ din drumul ({$1, 2, 4, 5$}) putem sa deviem din $4$ prin ({$7, 3, 5$}), formand drumul ({$1, 2, 4, 7, 3, 5$}). Este intuitiv ca, la fiecare pas, pentru fiecare nod din arbore este interesant doar cel mai scurt drum de deviatie.