מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/אלגוריתם Dijkstra/תרגילים/מציאת מסלול זול בגרף בעל קשתות בתחום שלם קטן/שאלה

$\displaystyle k$ הוא קבוע שלם חיובי כלשהו (לדוגמה 3), שאינו גדל יחד עם שאר הנתונים בשאלה (כגון מספר הצמתים או הקשתות).

נתונים גרף מכוון $\displaystyle G=(V,E)$ ברשימת שכנויות, טבלת עלויות לקשתות $\displaystyle E$, וצומת מוצא $\displaystyle s\in V$ כלשהו. ידוע שעלות כל קשת היא מספר שלם חיובי כלשהו הלקוח מהתחום $\displaystyle [1,k]$.

בהינתן צומת $\displaystyle v\in V$ כלשהו, רוצים לדעת מהו המסלול הזול ביותר מ$\displaystyle s$ ל$\displaystyle v$. אנא כתוב אלגוריתם יעיל לצורך כך.