Η ζωή είναι πολύπλοκη οι αφαιρέσεις, όπως τα γραφήματα, τα μήκη ακμών,και οι συντομότερες διαδρομές, σπανίως απεικονίζουν ολόκληρη την αλήθεια. Φανταστείτε  σε ένα δίκτυο επικοινωνιών, ακόμα και αν τα μήκη των  ακμών αντανακλούν πιστά τις καθυστερήσεις μετάδοσης, μπορεί να υπάρχουν άλλες σκοπιμότητες οι οποίες να εμπλέκονται στην επιλογή μιας διαδρομής.

Για παράδειγμα κάθε επιπλέον ακμή στη διαδρομή μπορεί να είναι ένας επιπλέον "σταθμός" γεμάτος αβεβαιότητες και κινδύνους απώλειας πακέτων. Σε τέτοιες περιπτώσεις θα θέλαμε να αποφύγουμε διαδρομές με πάρα πολλές ακμές. Αυτό το πρόβλημα, αν το απεικονίζαμε σε ένα γράφημα, στο οποίο η συντομότερη διαδρομή από τον κόμβο S στον κόμβο T έχει τέσσερις ακμές ενώ υπάρχει μία άλλη διαδρομή η οποία έχει κάπως μεγαλύτερο μήκος αλλά χρησιμοποιεί μόνο δύο ακμές.

Αν οι τέσσερις ακμές μεταφράζονται σε απαγορευτική αναξιοπιστία πρέπει να χρειαστεί να επιλέξουμε την τελευταία διαδρομή.

Υποθέστε λοιπόν ότι ότι μας δίνεται ένα γράφημα G με μήκη στις ακμές, μαζί με δύο κόμβους s και t έναν ακέραιο k, και θέλουμε τη συντομότερη διαδρομή από τον s στον t η οποία να χρησιμοποιεί το πολύ k ακμές.

Υπάρχει κάποιος γρήγορος τρόπος για να προσαρμόσουν τον αλγόριθμο του Dijkstra σε αυτή τη νέα εργασία; μάλλον όχι. Εκείνος ο αλγόριθμος εστιάζει στο μήκος κάθε συντομότερης διαδρομής χωρίς να θυμάται το πλήθος των σταθμών στη διαδρομή,  κάτι που τώρα αποτελεί κρίσιμη πληροφορία.

Στον δυναμικό προγραμματισμό το τέχνασμα είναι να επιλέγουμε ύπο-προβλήματα έτσι ώστε να απομνημονεύονται και να μεταφέρονται όλες τις ζωτικές πληροφορίες.

Στην προκειμένη περίπτωση ας ορίσουμε για κάθε κορφή v και κάθε  ακέραιο i μικρότερο και ίσο του k  το dist(v,i) ως μήκος της συντόμευσης διαδρομής από το s στο v η οποία χρησιμοποιεί i ακμές.

Οι αρχικές τιμές του dist(v,0) είναι άπειρες για όλες τις κορφές εκτός της s για την οποία είναι μηδέν. Και γενική εξίσωση ενημέρωσης είναι

dist(v,i) =min{dist(u,i-1)+l(u,v) }