האלגוריתם של ג'ונסון

האלגוריתם של ג'ונסון מוצא מסלולים קצרים בין כל זוג צמתים בגרף מכוון וממושקל. הוא מותאם במיוחד לגרפים דלילים, כלומר כאלה שיש בהם יחסית מעט קשתות.

הרעיון הבסיסי הוא להריץ את אלגוריתם דייקסטרה (אלגוריתם למציאת המסלול הקצר ביותר מצומת מקור כאשר כל המשקלים אי‑שליליים) מכל צומת בגרף. מכיוון שדייקסטרה דורש משקלים אי‑שליליים, ג'ונסון מבצע תיקון משקלות קודם.

מגדירים פונקציה h שמקצה לכל צומת מספר ממשי. המשקל החדש של קשת מ‑u ל‑v מוגדר כ־w'(u,v)=w(u,v)+h(u)-h(v). שינוי זה שומר על סדר מסלולים לפי אורכם, כלומר מסלולים קצרים בבסיס יישארו קצרים גם אחרי התיקון.

כדי למצוא את h מריצים את אלגוריתם בלמן‑פורד (אלגוריתם היכול לטפל בקשתות עם משקל שלילי ומזהה מעגלים שליליים). מוסיפים צומת s חדש עם קשתות משקל 0 אל כל צומת, מריצים בלמן‑פורד מ‑s, ובודקים האם קיים מעגל שלילי. אם קיים, האלגוריתם מדווח ועוצר. אם לא, מגדירים h(u) כשווי המסלול הקצר מ‑s ל‑u, מתקנים את המשקלים ומריצים דייקסטרה מכל צומת.

דייקסטרה במימוש טוב רץ ב‑O(E + V log V). מריצים אותה V פעמים, לכן חלק זה עולה O(VE + V^2 log V). בלמן‑פורד רץ ב‑O(VE) ופועל רק פעם אחת, ולכן אינו מעלה את הסדר הכולל של הריצה. כשמדובר בגרף דליל (E קטן בהרבה מ‑V^2), סיבוכיות ג'ונסון נמוכה מ‑O(V^3), ולכן הוא מהיר יותר מפלויד‑וורשאל במצבים כאלה.

אלגוריתם ג'ונסון מוצא את הדרך הכי קצרה בין כל שתי נקודות בגרף. גרף הוא אוסף נקודות וקווים עם משקל.

הרעיון הוא להשתמש בדייקסטרה. דייקסטרה מוצא דרכים קצרות, אבל עובד רק כשהמשקלים לא שליליים. לכן קודם עושים תיקון משקלים בעזרת בלמן‑פורד. בלמן‑פורד יכול לעבוד גם עם משקלים שליליים והוא גם מגלה אם יש מעגל שלילי. מעגל שלילי זה לולאה שמקטינה את סכום המשקלים שוב ושוב, ואז אין דרך הכי קצרה.

המטרה היא: להוסיף נקודה חדשה s שמחוברת לכל הנקודות בקווים שמשקלם 0, להריץ בלמן‑פורד מ‑s ולקבל מספרים h לכל נקודה. משתמשים ב‑h כדי לשנות את המשקלים כך שיהיו לא שליליים. אחרי זה מריצים דייקסטרה מכל נקודה ומוצאים את כל הדרכים הקצרות.

בלמן‑פורד פועל רק פעם אחת. דייקסטרה רץ פעם על כל נקודה. כשיש מעט קווים בגרף, השיטה של ג'ונסון בדרך כלל מהירה יותר משיטות אחרות כמו פלויד‑וורשאל.