Network Delay Time

Q: מהי סיבוכיות הזמן של Network Delay Time?

באמצעות האלגוריתם של דייקסטרה וערימה בינארית, סיבוכיות הזמן היא O(E log E) , כאשר E הוא מספר הקישורים. זה שווה ל־ O(E log n) , מכיוון ש־E לכל היותר n². סיבוכיות המקום היא O(n + E) . זמן הריצה של Bellman-Ford הוא O(n · E) .

Q: למה האלגוריתם של דייקסטרה זקוק למשקלים לא שליליים?

דייקסטרה לעולם אינו מבקר מחדש בצומת שנקבע, וזה בטוח רק אם אין מסלול מאוחר יותר שיכול להיות קצר יותר. עם קישורים A → B שזמנם 2, A → C שזמנם 3 ו- C → B שזמנו -2, הוא קובע את B במרחק 2, אך המסלול דרך C מגיע אליו במרחק 1. בלמן-פורד מתמודד עם זמנים שליליים.

Q: האם תוכל לפתור את בעיית זמן ההשהיה ברשת בלי ערימת עדיפויות?

כן. דייקסטרה עם מערך רגיל סורק כל צומת שעדיין לא נקבע עבור הזמן הקטן ביותר, וזה עולה O(n²) בסך הכול. הוא עדיף בגרפים צפופים, שבהם E קרוב ל־n². בגרפים דלילים, למשל עם 3,000 צמתים ו־4,000 קישורים, גרסת הערימה מבצעת הרבה פחות עבודה.

בינונימסלולים קצרים ביותר גרפים ערימה

+10

ברשת יש n צמתים שמסומנים במספרים 1 עד n. הקישור times[i] = [u, v, w] מעביר אות מצומת u לצומת v במשך w יחידות זמן, בכיוון הזה בלבד.

אות יוצא מצומת k בזמן 0 ונע לאורך כל הקישורים האפשריים. החזירו את הזמן שבו הצומת האחרון מקבל אותו, או -1 אם צומת כלשהו לעולם לא מקבל אותו.

פונקציה

networkDelayTime(times: integer-2d-array, n: integer, k: integer) → integer

timesinteger-2d-array: הקשתות המכוונות, כל אחת בצורה [u, v, w]
ninteger: מספר הצמתים
kinteger: הצומת ששולח את האות
מחזירהinteger: הזמן שבו הצומת האחרון מקבל את האות, או ‎-1

אילוצים

2 ≤ n ≤ 3000
1 ≤ times.length ≤ 4000
times[i].length = 3
1 ≤ u, v ≤ n and u ≠ v
0 ≤ w ≤ 100
אין שני קישורים שחולקים גם את אותו u וגם את אותו v.
1 ≤ k ≤ n

דוגמאות

קלט: times = [[1, 2, 4], [1, 3, 1], [3, 2, 2], [2, 4, 1]]n = 4k = 1
פלט: 4
הסבר: הקישור הישיר מגיע לצומת 2 בזמן 4, אבל המסלול דרך צומת 3 מגיע בזמן 1 + 2 = 3. צומת 4 מקבל את האות אחרון, בזמן 3 + 1 = 4.

שאלת המשך

נניח שהאות דועך לאחר שהוא עובר m קישורים. איך מוצאים את הזמן שבו הצומת האחרון שומע אותו, תחת המגבלה הזאת?

רמזים

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

נפתחו 0 מתוך 3

פתרון

כל צומת מקבל את האות לאחר זמן השווה לאורך המסלול המהיר ביותר שלו מ־k, לכן מדובר בבעיית המסלולים הקצרים ביותר ממקור יחיד ולאחריה מציאת המקסימום, או ‎-1 כשאין מסלול לצומת. זמני הקישורים לעולם אינם שליליים, לכן האלגוריתם של דייקסטרה מבקר בכל צומת פעם אחת. להלן, E הוא times.length.

חיפוש לעומק שחוזר לבקר בכל מסלול מהיר יותר

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

האינטואיציה

חפשו מ־k באמצעות חיפוש לעומק, תוך שמירת הזמן שהצטבר עד כה, ותעדו את זמן ההגעה המהיר ביותר לכל צומת. מסלול שמגיע לצומת בזמן שאינו מוקדם יותר מהזמן המתועד נעצר; מסלול מהיר יותר מעדכן את התיעוד וממשיך בחיפוש. כל תיעוד מסתיים בזמן המהיר ביותר בפועל, כי המסלול המהיר ביותר משפר אותו בשלב כלשהו.

צומת יכול להשתפר פעמים רבות. הציבו 18 שערים בשורה, כשכל זוג מחובר בקישור חינמי וגם במסלול עוקף שעלותו 65,536, 32,768 וכן הלאה עד 1. כשמנסים תחילה את המסלולים העוקפים, החיפוש מגיע לשער האחרון ב־131,072 זמנים שונים, ועובר בכל מה שמאחוריו בכל פעם: העבודה גדלה באופן מעריכי ביחס ל־n.

אלגוריתם

הגדר את כל הזמנים הטובים ביותר לאינסוף ודחוף (k, 0) למחסנית.
הוצא (node, t) מהמחסנית. דלג עליו אלא אם t < best[node]; לאחר מכן הגדר best[node] = t.
דחוף (next, t + w) עבור כל קישור מ־node שזמן ההגעה דרכו טוב יותר מ־best[next].
כשהמחסנית ריקה, החזר -1 אם אחד מהזמנים הטובים ביותר הוא אינסופי; אחרת החזר את הגדול ביותר.

def networkDelayTime(times, n, k):
    graph = [[] for _ in range(n + 1)]
    for u, v, w in times:
        graph[u].append((v, w))
    INF = float("inf")
    best = [INF] * (n + 1)  # the fastest arrival found so far at each node
    stack = [(k, 0)]
    while stack:
        node, t = stack.pop()
        # A route that is not faster than one already found adds nothing.
        if t >= best[node]:
            continue
        best[node] = t
        # Push in reverse so the first listed edge is explored first.
        for nxt, w in reversed(graph[node]):
            if t + w < best[nxt]:
                stack.append((nxt, t + w))
    worst = 0
    for node in range(1, n + 1):
        if best[node] == INF:
            return -1
        worst = max(worst, best[node])
    return worst

Bellman-Ford: בצע הרפיה לכל קישור עד n-1 פעמים

האינטואיציה

שמרו זמן משוער dist לכל צומת, 0 עבור k. הרפיית קישור u → v מורידה את dist[v] ל־dist[u] + w כאשר הערך הזה קטן יותר. Bellman-Ford מרפה כל קישור בכל מעבר.

קחו את המסלול המהיר ביותר לצומת, נניח k → a → b → v. המעבר הראשון קובע את dist[a], השני את dist[b], והשלישי את dist[v]. מסלול מהיר ביותר לעולם אינו עובר שוב באותו צומת, ולכן יש בו לכל היותר n-1 קישורים, ו־n-1 מעברים מספיקים כדי לקבוע את הערך עבור כל צומת.

העלות של כל מעבר היא O(E). שרשרת של 3,000 צמתים שמופיעה בסדר מהקצה המרוחק שלה לאחור דורשת 2,999 מעברים על פני 4,000 קישורים: בערך 12 מיליון הרפיות.

אלגוריתם

הגדר dist[k] = 0 ואת כל שאר ערכי dist לאינסוף.
חזור על הפעולה עד n-1 פעמים: עבור כל קשת [u, v, w], אם dist[u] + w < dist[v], הגדר dist[v] = dist[u] + w.
עצור מוקדם אם עובר אחד לא משנה דבר.
החזר ‎-1 אם אחד מערכי dist עדיין אינסופי, אחרת החזר את הגדול ביותר.

def networkDelayTime(times, n, k):
    INF = float("inf")
    dist = [INF] * (n + 1)
    dist[k] = 0
    # A fastest route visits each node at most once, so it has at most n-1 edges,
    # and n-1 passes over every edge are enough to find it.
    for _ in range(n - 1):
        changed = False
        for u, v, w in times:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                changed = True
        if not changed:  # a pass that improves nothing means every time is final
            break
    worst = 0
    for node in range(1, n + 1):
        if dist[node] == INF:
            return -1
        worst = max(worst, dist[node])
    return worst

האלגוריתם של דייקסטרה עם ערימת מינימום

האינטואיציה

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

ערימת מינימום מוצאת את הזמן הקטן ביותר. כשצומת משתפר, דוחפים רשומה חדשה ומשאירים את הישנה במקומה; רשומה שנשלפה והזמן שלה גדול מ־dist היא מיושנת, ולכן מדלגים עליה. כל קישור דוחף לכל היותר רשומה אחת, ולכן הערימה מכילה לכל היותר E + 1 רשומות, והזמן הכולל הוא O(E log E).

אלגוריתם

הגדר dist[k] = 0, כל ערך אחר של dist לאינסוף, והכנס את (0, k) לערימת מינימום.
הוצא את (t, node) הקטן ביותר; אם t > dist[node], דלג עליו כי הוא מיושן.
עבור כל קישור node → next עם זמן w, אם t + w < dist[next], הגדר dist[next] = t + w והכנס את (t + w, next).
כשהערימה ריקה, החזר -1 אם אחד מערכי dist הוא אינסופי; אחרת החזר את הגדול ביותר.

import heapq


def networkDelayTime(times, n, k):
    graph = [[] for _ in range(n + 1)]
    for u, v, w in times:
        graph[u].append((v, w))
    INF = float("inf")
    dist = [INF] * (n + 1)
    dist[k] = 0
    heap = [(0, k)]  # (arrival time, node), smallest time on top
    while heap:
        t, node = heapq.heappop(heap)
        # A stale entry: this node was already reached sooner.
        if t > dist[node]:
            continue
        # t is now final: every other route reaches node later.
        for nxt, w in graph[node]:
            if t + w < dist[nxt]:
                dist[nxt] = t + w
                heapq.heappush(heap, (t + w, nxt))
    worst = 0
    for node in range(1, n + 1):
        if dist[node] == INF:
            return -1
        worst = max(worst, dist[node])
    return worst

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

התייחסות לקישורים כאילו הם דו־כיווניים. [3, 1, 2] מעביר את האות מ־3 ל־1 בלבד, ולכן צומת 3 לא מקבל אותו בדוגמה השנייה.
שימוש בחיפוש רגיל לרוחב. הוא מוצא את המסלול עם מספר הקישורים הקטן ביותר: בדוגמה הראשונה הוא נותן לצומת 2 זמן 4 במקום 3.
שכחת ה־-1. חישוב המקסימום ללא בדיקה מחזיר אינסוף, או מסתיר את הצומת שמעולם לא קיבל את האות.
שימוש במספר השלם הגדול ביותר כאינסוף. dist[u] + w יגרום לגלישה למספר שלילי עבור u שלא הגיעו אליו; יש לדלג על צמתים שלא הגיעו אליהם או להשתמש ב־10^9.

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

מהי סיבוכיות הזמן של Network Delay Time?

באמצעות האלגוריתם של דייקסטרה וערימה בינארית, סיבוכיות הזמן היא O(E log E), כאשר E הוא מספר הקישורים. זה שווה ל־O(E log n), מכיוון ש־E לכל היותר n². סיבוכיות המקום היא O(n + E). זמן הריצה של Bellman-Ford הוא O(n · E).

למה האלגוריתם של דייקסטרה זקוק למשקלים לא שליליים?

דייקסטרה לעולם אינו מבקר מחדש בצומת שנקבע, וזה בטוח רק אם אין מסלול מאוחר יותר שיכול להיות קצר יותר. עם קישורים A → B שזמנם 2, A → C שזמנם 3 ו-C → B שזמנו -2, הוא קובע את B במרחק 2, אך המסלול דרך C מגיע אליו במרחק 1. בלמן-פורד מתמודד עם זמנים שליליים.

האם תוכל לפתור את בעיית זמן ההשהיה ברשת בלי ערימת עדיפויות?

כן. דייקסטרה עם מערך רגיל סורק כל צומת שעדיין לא נקבע עבור הזמן הקטן ביותר, וזה עולה O(n²) בסך הכול. הוא עדיף בגרפים צפופים, שבהם E קרוב ל־n². בגרפים דלילים, למשל עם 3,000 צמתים ו־4,000 קישורים, גרסת הערימה מבצעת הרבה פחות עבודה.

def networkDelayTime(times, n, k):
    # כתבו כאן את הקוד

בדיקה #1

בדיקה #2

בדיקה #3

ארגומנטים

times = [[1, 2, 4], [1, 3, 1], [3, 2, 2], [2, 4, 1]]
n = 4
k = 1

הפלט הצפוי

Network Delay Time

פונקציה

אילוצים

דוגמאות

רמזים

פתרון

חיפוש לעומק שחוזר לבקר בכל מסלול מהיר יותר

Bellman-Ford: בצע הרפיה לכל קישור עד n-1 פעמים

האלגוריתם של דייקסטרה עם ערימת מינימום

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

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

בעיות דומות