האלגוריתם של דייקסטרה הובס (לפעמים)
במשך עשורים, האלגוריתם של דייקסטרה למציאת המסלולים הקצרים ביותר נחשב לאחד האלגוריתמים הבסיסיים הקלאסיים.
ובכן, הוא כבר לא (תמיד) כזה.
קבוצת חוקרים מסין הציגה לאחרונה אלגוריתם חדש, שיכול, בסיטואציות מסויימות, לרוץ בסיבוכיות נמוכה יותר.
האלגוריתם המקורי מחליט בכל שלב על נתיב אחד שהוא "מוחלט" באופן שמבצע בפועל מיון של כלל הקשתות במערכת. האלגוריתם החדש מציע לרוץ בכל פעם מספר צעדים קדימה, באופן שיכול "לחלט" מספר מסלולים יחד. באופן הזה, ניתן להגיע להחלטה על כלל המסלולים, מבלי לבצע מיון מלא — וכך, במקרים מסויימים, להגיע לסיבוכיות נמוכה יותר.
האלגוריתם של דייקסטרה עדיין נחשב (ומוכח) לאלגוריתם הכללי בעל הסיבוכיות הנמוכה ביותר שניתן להריץ על כל מערכת מסלולים שהיא. ובכל זאת, זוהי פריצת דרך אמיתית שמשנה את ספרי הלימוד של מדעי המחשב.
Tsinghua University's Duan Ran-led team's new shortest path algorithm breaks sorting bottleneck, wins Best Paper Award at STOC.
