נתון גרף מכוון G=(V,E) עם משקלים אי-שליליים c(e)≥0 על הצלעות ונתון קדקוד מסוים r∈V. הביטו באלגוריתם הבא:
(i) מאתחלים מערך חד-ממדי A באמצעות הכלל:
A[v]={0,∞,v=rv=r
(ii) לולאה חיצונית: חוזרים שוב ושוב על הפעולה הבאה.
(ii.1) לולאה פנימית: סורקים את הצלעות בסדר לקסיקוגרפי. לכל צלע e=(u,v)∈E מבצעים:
אם A[v]>A[u]+c(e) אז מעדכנים A[v]←A[u]+c(e).
(ii.2) אם בהרצה הנוכחית של כל הלולאה הפנימית לא בוצע אף עדכון, אז האלגוריתם מסיים.
(א) רישמו מה מחשב האלגוריתם (אין צורך להוכיח נכונות).
(ב) יהי B(n) המספר המרבי של איטרציות שמתבצעות בלולאה החיצונית על גרפים בעלי n קדקודים. חשבו את B(n), והציגו סדרת גרפים Gn עליהם מתבצעות בדיוק B(n) איטרציות.
(ג) הציגו סדרת גרפים אחרת Gn′, עבורם נכנסים ללולאה החיצונית פעמיים בלבד, וזאת למרות ששמספר הצלעות שלהם זהה לגרפים מהסעיף הקודם, כלומר ∣E(Gn′)∣=∣E(Gn)∣ לכל n.