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

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

האלגוריתם נקרא על שמו של [[דונלד ב. ג'ונסון]], אשר פרסם אותו בשנת 1977{{הערה|{{citation|first=Donald B.|last=Johnson|authorlink=Donald B. Johnson|title=Efficient algorithms for shortest paths in sparse networks|journal=[[Journal of the ACM]]|volume=24|issue=1|pages=1–13|year=1977}}}}.

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

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

כדי למצוא פונקציה <math>\ h</math> שתבטיח שהמשקלים בגרף החדש יהיו כולם חיוביים, אלגוריתם ג'ונסון משתמש ב[[אלגוריתם בלמן-פורד]] בדרך הבאה: ראשית הוא מוסיף לגרף המקורי צומת חדש <math>\ s</math> ומוסיף קשת במשקל 0 מ-<math>\ s</math> אל כל <math>\ v\isin V</math>. כעת הוא מריץ את אלגוריתם בלמן פורד על הצומת <math>\ s</math>. אם האלגוריתם מתריע על מעגל שלילי, אלגוריתם ג'ונסון מודיע זאת ומפסיק. אחרת, הוא משתמש בתוצאת אלגוריתם בלמן פורד כדי להגדיר את הפונקציה <math>\ h</math> כך: <math>\ h(u)=\delta(s,u)</math> כאשר <math>\ \delta(s,u)</math> הוא משקל המסלול הקל ביותר מ-<math>\ s</math> אל <math>\ u</math>. לאחר תיקון המשקלות בגרף המקורי מריץ אלגוריתם ג'ונסון את אלגוריתם דייקסטרה על כל הצמתים, כמתואר לעיל.

[[קובץ:Johnson's algorithm.svg|מרכז|ממוזער|650px|משמאל לימין: הגרף המקורי עם משקלות שליליים ; הוספת צומת חדש <math>\ q</math> וקשת במשקל 0 מ-<math>\ q</math> אל כל <math>\ v\isin V</math> והרצת אלגוריתם בלמן פורד על הצומת <math>\ q</math> ; תיקון המשקלות בגרף המקורי]]

==סיבוכיות זמן==
כיוון ש[[סיבוכיות זמן|סיבוכיות הזמן]] של אלגוריתם דייקסטרה היא <math>\ O(E+V\log V)</math> במימוש האופטימלי שלו, והאלגוריתם מורץ <math>\ V</math> פעמים (פעם אחת לכל אחד מהצמתים), סיבוכיות הזמן של חלק זה של האלגוריתם היא <math>\ O(VE+V^2\log V)</math>. סיבוכיות בלמן פורד היא <math>\ O(VE)</math> ומכיוון שהוא מורץ רק פעם אחת הוא אינו משפיע על זמן ריצת האלגוריתם.

כאשר הגרף דליל, כלומר מבחינה פורמלית מתקיים <math>\ E \in o(V^2)</math>, סיבוכיות האלגוריתם של ג'ונסון תהיה נמוכה מ-<math>\ O(V^3)</math>, שהיא הסיבוכיות של אלגוריתמים אחרים לפתרון בעיית המסלולים הקצרים ביותר בין כל שני זוגות צמתים, דוגמת [[האלגוריתם של פלויד-וורשאל]].

==קישורים חיצוניים==
{{ויקישיתוף בשורה}}

==הערות שוליים==
{{הערות שוליים|יישור=שמאל}}

[[קטגוריה:אלגוריתמים בתורת הגרפים]]