Floyd Warshall Algorithm

+10

נתון גרף מכוון עם n צמתים, שממוספרים מ־0 עד n-1, כמטריצה בגודל n על n: הערך matrix[i][j] הוא המשקל של הקשת מהצומת i לצומת j, או -1 כשאין קשת כזו, ו־matrix[i][i] הוא 0. אורך של מסלול הוא סכום המשקלים של הקשתות שלו.

החזר מטריצה בגודל n על n, שבה הערך [i][j] הוא אורך המסלול הקצר ביותר מהצומת i לצומת j, או -1 כאשר לא ניתן להגיע לצומת j מהצומת i.

פונקציה

shortestDistances(matrix: integer-2d-array) → integer-2d-array

matrixinteger-2d-array: משקלי הקשתות: <code>matrix[i][j]</code> הוא משקל הקשת מ־<code>i</code> אל <code>j</code>, או ‎-1 כשאין קשת
מחזירהinteger-2d-array: המרחק הקצר ביותר בין כל זוג צמתים, ‎-1 כשאין מסלול

אילוצים

1 ≤ n ≤ 100, כאשר n = matrix.length = matrix[i].length
matrix[i][i] = 0
עבור i ≠ j, matrix[i][j] הוא -1 (אין קשת) או 0 ≤ matrix[i][j] ≤ 1000.
הקשתות הן חד־כיווניות: matrix[i][j] ו־matrix[j][i] אינן תלויות זו בזו.

דוגמאות

קלט: matrix = [[0, 4, 11, -1], [-1, 0, 2, 9], [1, -1, 0, 3], [-1, -1, -1, 0]]
פלט: [[0, 4, 6, 9], [3, 0, 2, 5], [1, 5, 0, 3], [-1, -1, -1, 0]]
הסבר: דרך צומת 1, צומת 0 מגיע לצומת 2 בעלות 6 במקום 11, ולצומת 3 בעלות 9. צומת 1 מגיע לצומת 0 דרך צומת 2 בעלות 3. שום דבר לא יוצא מצומת 3, ולכן הערך בשורה שלו הוא ‎-1‎ מחוץ לאלכסון.

קלט: matrix = [[0, 6, 1], [-1, 0, -1], [-1, 0, 0]]
פלט: [[0, 1, 1], [-1, 0, -1], [-1, 0, 0]]
הסבר: הקשת מ-2 ל-1 שוקלת 0, לכן 0 → 2 → 1 עולה 1, פחות מהמסלול הישיר שעולה 6. אין קשת שיוצאת מצומת 1 או נכנסת לצומת 0, לכן הזוגות האלה נשארים -1.

שאלת המשך

אחרי שבנית את הטבלה, העלות של קשת אחת יורדת. האם תוכל לעדכן כל מרחק ב־O(n²) במקום להריץ שוב את הלולאות של O(n³)?

רמזים

פתחו אותם אחד אחד. כל רמז חושף קצת יותר.

נפתחו 0 מתוך 3

פתרון

צריך למצוא את המסלול הקצר ביותר לכל זוג צמתים. אלגוריתם Floyd-Warshall מוצא את כל n² התשובות באמצעות לולאה משולשת אחת. בכל סיבוב, המסלולים יכולים לעבור דרך צומת נוסף, והעלות היא השוואה אחת לכל זוג: המסלול הטוב ביותר עד כה לעומת המסלול שעובר דרך הצומת החדש.

האריכו כל מסלול בקשת אחת, עד ששום דבר לא משתנה

נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר

האינטואיציה

מתחילים מהמטריצה, ובכל מעבר מאריכים כל מסלול בקשת אחת: מסלול מ־i ל־m יחד עם הקשת m → j הוא מסלול מ־i ל־j, ושומרים אותו אם הוא קצר יותר. חוזרים על כך עד שמעבר לא משנה דבר.

אחרי p מעברים, נמצא כל מסלול קצר ביותר שאורכו עד p+1 קשתות. אף משקל אינו שלילי, ולכן יש מסלול קצר ביותר ללא לולאה ובו לכל היותר n-1 קשתות, והמעברים נעצרים כשכל המרחקים סופיים. מעבר אחד הוא n³ = 10^6 צעדים עבור 100 צמתים, ושרשרת ארוכה של מסלולים קצרים ביותר דורשת עד n מעברים: O(n⁴), עד 10^8 צעדים.

אלגוריתם

העתק את matrix לתוך dist.
עבור כל i, m ו-j: אם dist[i][m] וגם matrix[m][j] קיימים, חשב את הסכום שלהם.
אם dist[i][j] הוא -1 או גדול מהסכום, שמור את הסכום וזכור שהמעבר שינה משהו.
חזור על המעבר עד שהוא לא משנה דבר, ואז החזר את dist.

def shortestDistances(matrix):
    n = len(matrix)
    # dist starts as the routes of one edge; -1 means no route found yet.
    dist = [row[:] for row in matrix]
    changed = True
    while changed:
        changed = False
        # One pass: a route from i that ends at m may grow by the edge m -> j.
        for i in range(n):
            for m in range(n):
                if dist[i][m] == -1:
                    continue
                for j in range(n):
                    edge = matrix[m][j]
                    if edge == -1:
                        continue
                    via = dist[i][m] + edge
                    if dist[i][j] == -1 or via < dist[i][j]:
                        dist[i][j] = via
                        changed = True
    return dist

Floyd-Warshall: לאפשר תחנה אחת נוספת בכל סבב

האינטואיציה

הגבל אילו צמתים מסלול יכול לעצור בהם בין נקודות הקצה שלו. הטבלה מתחילה כמטריצה, כלומר המסלולים ללא עצירות. אחרי סבב k, הערך dist[i][j] הוא המסלול הקצר ביותר שכל העצירות בו נמצאות בצמתים 0 עד k, והסבב האחרון נותן את התשובה.

בסבב k, המסלול הטוב ביותר שיכול גם לעצור ב-k או מדלג על k, והטבלה כבר מכילה אותו, או עובר דרך k פעם אחת, מכיוון שאין משקלים שליליים. שתי מחציות המסלול עוצרות רק בצמתים 0 עד k-1, ולכן הן dist[i][k] ו-dist[k][j].

בדוגמה הראשונה, סבב 1 מחליף את המסלול הישיר באורך 11 מצומת 0 לצומת 2 במסלול באורך 6. סבב 2 נותן מסלול באורך 6 + 3 = 9 מצומת 0 לצומת 3, עם עצירה בצומת 1 בתוך המסלול באורך 6.

טבלה אחת מספיקה: השורה k והעמודה k אינן משתנות בסבב k, כי dist[k][k] הוא 0.

אלגוריתם

העתק את matrix אל dist; ‏-1 פירושו שעדיין לא נמצא מסלול.
עבור k מ-0 עד n-1, ועבור כל i ו-j: דלג על הזוג אם dist[i][k] או dist[k][j] הם ‎-1.
אחרת, חשב via = dist[i][k] + dist[k][j].
אם dist[i][j] הוא ‎-1 או גדול מ-via, הצב בו את via.
החזר את dist.

def shortestDistances(matrix):
    n = len(matrix)
    # dist starts as the direct edges; -1 means no route found yet.
    dist = [row[:] for row in matrix]
    # After round k, dist[i][j] is the cheapest route whose stops all lie in 0..k.
    for k in range(n):
        for i in range(n):
            if dist[i][k] == -1:
                continue
            for j in range(n):
                if dist[k][j] == -1:
                    continue
                via = dist[i][k] + dist[k][j]
                if dist[i][j] == -1 or via < dist[i][j]:
                    dist[i][j] = via
    return dist

מלכודות ומקרי קצה

הוספת ‎-1 כאילו היה משקל: -1 + 5 = 4 נראית כמו מסלול. בדקו קודם את שני החלקים, והתייחסו ל־‎-1 ב־dist[i][j] כאל ערך גרוע יותר מכל מסלול.
הצבת הלולאה על k בפנים. מסלולים דרך התחנות 0 עד k-1 חייבים להיות סופיים לפני שמציעים את הצומת k.
שימוש בערך int הגדול ביותר כאינסוף: חיבור של שני ערכים כאלה גורם לגלישה של int בן 32 סיביות, והתוצאה היא מרחק שלילי. מרחק אמיתי הוא לכל היותר 99 × 1000 = 99,000, לכן 10^9 בטוח, כי 2 × 10^9 קטן מ־2^31-1.
הנחה שקשתות פועלות בשני הכיוונים. בדוגמה השנייה, צומת 0 מגיע לצומת 1, אבל מצומת 1 אי אפשר להגיע לשום צומת.
הרצת חיפוש לרוחב, שמתעלם ממשקלים: בדוגמה הראשונה הוא מדווח על מרחק 11 מצומת 0 לצומת 2, ולא על 6.

שאלות נפוצות3

מהי סיבוכיות הזמן של אלגוריתם Floyd Warshall?

זמן O(n³) עבור n צמתים: שלוש לולאות מקוננות שעוברות על הצמתים, עם חיבור אחד והשוואה אחת בכל צעד, 10^6 צעדים עבור 100 צמתים. המקום הוא O(n²) עבור טבלת המרחקים, שאפשר לעדכן במקום.

האם Floyd Warshall עובד עם משקלי קשת שליליים?

כן, כל עוד אין מעגל שלילי — לולאה שסכום המשקלים שלה קטן מ־0. כשיש מעגל שלילי, המסלולים הקצרים ביותר אינם מוגדרים, והטבלה מציגה זאת: חלק מהערכים של dist[i][i] מסתיימים מתחת ל־0.

מתי כדאי להשתמש ב-Floyd Warshall במקום באלגוריתם דייקסטרה?

השתמשו באלגוריתם Floyd-Warshall עבור כל זוג צמתים בגרף צפוף שמכיל עד כמה מאות צמתים. הפעלת Dijkstra מכל צומת עולה O(n³) עם מערך ו־O(n · E log n) עם ערימה, והיא עדיפה בגרפים גדולים ודלילים. Floyd-Warshall אינו זקוק לערימה ומקבל קשתות שליליות, בניגוד ל־Dijkstra.

def shortestDistances(matrix):
    # כתבו כאן קוד

בדיקה #1

בדיקה #2

ארגומנט

matrix = [[0, 4, 11, -1], [-1, 0, 2, 9], [1, -1, 0, 3], [-1, -1, -1, 0]]

הפלט הצפוי

[[0, 4, 6, 9], [3, 0, 2, 5], [1, 5, 0, 3], [-1, -1, -1, 0]]