דף הבית
אקראי
בסביבה
כניסה לחשבון
הגדרות
תרומה לוויקיפדיה
אודות ויקיפדיה
הבהרות משפטיות
חיפוש
פורטל
:
מדעי המחשב/תמונה נבחרת/44
שפה
מעקב
עריכה
<
פורטל:מדעי המחשב
|
תמונה נבחרת
השלבים הראשונים
באלגוריתם של ג'ונסון
למציאת מסלולים קצרים ב
גרף ממושקל
ומכוון בין כל שני זוגות צמתים.
משמאל לימין: הגרף המקורי עם משקלות שליליים ; הוספת צומת חדש
q
{\displaystyle \ q}
וקשת במשקל 0 מ-
q
{\displaystyle \ q}
אל כל
v
∈
V
{\displaystyle \ v\in V}
והרצת
אלגוריתם בלמן פורד
על הצומת
q
{\displaystyle \ q}
; תיקון המשקלות בגרף המקורי.