דמיינו שאתם נוסעים במסלול הקצר ביותר מנקודה לנקודה ולפתע גיליתם כי הנתיב שלפניכם חסום.
מה עלינו לעשות כעת? כיצד נחשב מסלול מחדש בצורה יעילה?
מתברר שישנם מחקרים רבים בתחום, ישנו מבנה נתונים שנקרא DSO = Distance Sensitivity Oracle אשר הינו מבנה נתונים שתופס מעט זכרון, ניתן לבנות אותו בזמן פולינומיאלי יעיל באופן יחסי, הוא מחשב את המסלול החלופי הקצר ביותר במדיוק או בקירוב טוב וזמן החישוב מחדש שלו הינו יעיל מאוד (אפילו בזמן לוגריתמי).
בסדנה זו אנו מממשים את מבנה הנתונים DSO כפי שפותח במהלך עבודת הדוקטורט של שראל כהן באוניברסיטת תל אביב במאמר שפורסם בכנס SODA'17. מבנה נתונים זה מבוסס על עץ חיפוש של מסלולים קצרים ביותר, התומך בנפילות של קשתות. אנו בודקים אמפירית את זמן הריצה של העיבוד המקדים (הזמן לבנות את מבנה הנתונים) וכן את זמן הריצה הממוצע כאשר מריצים 100,000 שאילתות.