פורטל:מדעי המחשב/תמונה נבחרת/44

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

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