Vi kan finne korteste veier fra hver node etter tur, men mange delinstanser vil overlappe; om vi har mange kanter, lønner det seg å bruke dynamisk programmering. Vi dekomponerer basert på hvor mange kanter vi får bruke i løsningen, eller hvilke noder som får inngå.