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