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

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

סיבוכיות זמן	O (|V|^2 \log |V| + |V||E|)
ממציא	דונלד ב. ג'ונסון
נקרא על שם	דונלד ב. ג'ונסון

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

האלגוריתם נקרא על שמו של דונלד ב. ג'ונסון, אשר פרסם אותו בשנת 1977^[1].

תיאור האלגוריתם

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

על כן, האלגוריתם "מתקן" את המשקלים בדרך הבאה: הוא מגדיר פונקציה ${\displaystyle \ h:V\to \mathbb {R} }$ שמתאימה לכל צומת מספר ממשי, ואז מתקנת באמצעותה את המשקל של כל קשת. אם משקל הקשת ${\displaystyle \ (u,v)}$ היה ${\displaystyle \ w(u,v)}$, היא מגדירה משקל חדש ${\displaystyle \ w'(u,v)=w(u,v)+h(u)-h(v)}$. ניתן להראות ששינוי זה של המשקלים לא משנה את התכונה המהותית שנחוצה בגרף - כל מסלול קל ביותר בגרף המקורי הוא קל ביותר גם בגרף החדש (תכונה זו אינה נשמרת אם מגדילים את משקלי כל הקשתות במספר קבוע אחד לכולן, למשל).

כדי למצוא פונקציה ${\displaystyle \ h}$ שתבטיח שהמשקלים בגרף החדש יהיו כולם חיוביים, אלגוריתם ג'ונסון משתמש באלגוריתם בלמן-פורד בדרך הבאה: ראשית הוא מוסיף לגרף המקורי צומת חדש ${\displaystyle \ s}$ ומוסיף קשת במשקל 0 מ-${\displaystyle \ s}$ אל כל ${\displaystyle \ v\in V}$. כעת הוא מריץ את אלגוריתם בלמן פורד על הצומת ${\displaystyle \ s}$. אם האלגוריתם מתריע על מעגל שלילי, אלגוריתם ג'ונסון מודיע זאת ומפסיק. אחרת, הוא משתמש בתוצאת אלגוריתם בלמן פורד כדי להגדיר את הפונקציה ${\displaystyle \ h}$ כך: ${\displaystyle \ h(u)=\delta (s,u)}$ כאשר ${\displaystyle \ \delta (s,u)}$ הוא משקל המסלול הקל ביותר מ-${\displaystyle \ s}$ אל ${\displaystyle \ u}$. לאחר תיקון המשקלות בגרף המקורי מריץ אלגוריתם ג'ונסון את אלגוריתם דייקסטרה על כל הצמתים, כמתואר לעיל.

משמאל לימין: הגרף המקורי עם משקלות שליליים ; הוספת צומת חדש ${\displaystyle \ q}$ וקשת במשקל 0 מ-${\displaystyle \ q}$ אל כל ${\displaystyle \ v\in V}$ והרצת אלגוריתם בלמן פורד על הצומת ${\displaystyle \ q}$ ; תיקון המשקלות בגרף המקורי

סיבוכיות זמן

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

כאשר הגרף דליל, כלומר מבחינה פורמלית מתקיים ${\displaystyle \ E\in o(V^{2})}$, סיבוכיות האלגוריתם של ג'ונסון תהיה נמוכה מ-${\displaystyle \ O(V^{3})}$, שהיא הסיבוכיות של אלגוריתמים אחרים לפתרון בעיית המסלולים הקצרים ביותר בין כל שני זוגות צמתים, דוגמת האלגוריתם של פלויד-וורשאל.

קישורים חיצוניים

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

הערות שוליים

1. Johnson, Donald B. (1977), "Efficient algorithms for shortest paths in sparse networks", Journal of the ACM, 24 (1): 1–13