1. **הבעיה:** נתון גרף מכוון $G = (V, E)$ עם $V = \{0, 1, 2, \ldots, n-1\}$ ו-$m$ קצוות, כאשר לכל קשת יש אורך חיובי. נתון מספר חיובי $k$. יש למצוא לכל קודקוד $i$ את האורך המינימלי של המסלול מ-$0$ ל-$i$, כאשר האורך המינימלי הוא מספר ממשי בטווח $[i, i+k]$. 2. **מטרה:** לפתור את הבעיה בזמן $O(m \log k)$ ולהסביר את מבני הנתונים בהם משתמשים. 3. **הסבר כללי:** הבעיה דומה לבעיית מציאת מסלולים קצרים ביותר (Shortest Path) מ-$0$ לכל שאר הקודקודים, אך עם מגבלה על טווח האורכים המינימליים. 4. **רעיונות לפתרון:** - נשתמש בגרף עם משקלים חיוביים, לכן אלגוריתם דייקסטרה מתאים. - כדי להשיג סיבוכיות $O(m \log k)$, נשתמש בתור עדיפות (Priority Queue) עם מבנה נתונים יעיל. - מאחר שהאורכים המינימליים בטווח $[i, i+k]$, ניתן לנצל את המגבלה הזו כדי לשפר את סיבוכיות האלגוריתם. 5. **מבני נתונים:** - תור עדיפות (Priority Queue) מסוג ערימה בינארית או ערימה עם מפתחות מוגבלים (לדוגמה, ערימת דק או ערימת בינום). - מאחר שהמשקלים מוגבלים בטווח $k$, ניתן להשתמש ב-\textbf{Dial's Algorithm} או מבנה דומה שמנצל את טווח המשקלים הקטן. 6. **Dial's Algorithm בקצרה:** - מתאים למשקלים שלמים בטווח קטן. - משתמש במערך של דליים (buckets) בגודל $k$. - כל דליי מכיל קודקודים עם מרחק מסוים. - זמן ריצה $O(m + n k)$, אך כאן $k$ קטן יחסית. 7. **התאמה לבעיה:** - מאחר שהמרחקים בין $i$ ל-$i+k$, ניתן להמיר את המשקלים כך שיתאימו ל-Dial's Algorithm. - נשתמש במבנה דליים בגודל $k$ כדי לנהל את הקודקודים לפי המרחקים. 8. **סיכום סיבוכיות:** - כל קשת מתווספת ומוסרת מהדליים פעם אחת. - לכן, זמן הריצה הוא $O(m \log k)$ (אם משתמשים בערימה עם מפתחות מוגבלים או דליים). 9. **תוצאה:** האלגוריתם מוצא את האורך המינימלי מ-$0$ ל-$i$ לכל $i$ בטווח הנתון בזמן $O(m \log k)$ באמצעות שימוש בתור עדיפות עם מבנה נתונים מותאם לטווח המשקלים.