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

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

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