Network Delay Time

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

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

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

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

Q: למה לא להשתמש ב־BFS עבור זמן השהיית רשת?

‏BFS מבקר בצמתים לפי מספר הקישורים שמפרידים ביניהם לבין נקודת ההתחלה, וזה תואם את זמן ההגעה רק כשכל קישור נמשך אותו פרק זמן. כאן זמני הקישורים שונים, ולכן מסלול עם יותר קישורים יכול להגיע מוקדם יותר. אם כל הזמנים היו שווים, BFS היה מספיק, וכשהזמנים הם רק 0 ו-1, ‏0-1 BFS המבוסס על deque עובד.

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

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

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

+10

לרשת יש n צמתים, שממוספרים מ־1 עד n. מקבלים את הקישורים שלה כרשימה times, כאשר 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 וגם 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
הסבר: צומת 3 שומע את האות בזמן 1. צומת 2 יכול לשמוע אותו בזמן 4 דרך הקישור הישיר שלו, אבל המסלול דרך צומת 3 מגיע בזמן 1 + 2 = 3, וצומת 4 שומע אותו בזמן 3 + 1 = 4. צומת 4 הוא האחרון, בזמן 4.

+16 בדיקות נסתרות בשליחה

שאלת המשך

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

רמזים

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

נפתחו 0 מתוך 3

פתרון

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

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

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

האינטואיציה

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

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

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

אלגוריתם

בנה רשימת שכנויות: עבור כל צומת, הקישורים שיוצאים ממנו והזמנים שלהם.
הגדר את הזמן הטוב ביותר של כל צומת לאינסוף ודחוף (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 עם זמן w פירושה: אם dist[u] + w קטן מ־dist[v], הקישור מציע דרך מהירה יותר אל v, ולכן מקטינים את dist[v] לערך הזה. Bellman-Ford מבצע מעברים על הרשימה כולה ומרפה כל קישור בכל מעבר.

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

כל מעבר עולה O(E), ולכן במקרה הגרוע הסיבוכיות היא O(n · E). סדר הרשימה קובע עד כמה הביצועים יהיו גרועים: אם הקישורים של מסלול ארוך אחד מופיעים ברשימה מהקצה הרחוק שלו בחזרה להתחלה, כל מעבר קובע את הערך הסופי של צומת אחד נוסף. אחד ממקרי הבדיקה הגדולים הוא בדיוק כזה: שרשרת בת 3,000 צמתים שמופיעה ברשימה בסדר הפוך, ודורשת 2,999 מעברים על פני 4,000 קישורים: בערך 12 מיליון הרפיות. בגודל כזה זה עדיין רץ בזמן, אבל כמות העבודה גדלה ביחס למכפלת n ב־E. היתרון של Bellman-Ford טמון במקום אחר: הוא נשאר נכון גם כשזמני קישורים מסוימים שליליים, מצב שבו Dijkstra נכשל.

אלגוריתם

הגדר את 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

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

האינטואיציה

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

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

ערימת מינימום מוצאת במהירות את הזמן הזמני הקטן ביותר. דוחפים (time, node) בכל פעם שהזמן של צומת משתפר, ומשאירים את הרשומה הישנה בערימה במקום לחפש אותה. כשהרשומה הישנה יוצאת מאוחר יותר, הזמן שלה גדול מהזמן הנוכחי של הצומת, ולכן מדלגים עליה. כל קשת דוחפת לכל היותר רשומה אחת, ולכן הערימה לעולם אינה מכילה יותר מ-E + 1 רשומות, וכל פעולת דחיפה או שליפה עולה O(log E). כך העלות הכוללת היא O(E log E), עם זיכרון של O(n + E) עבור רשימת השכנויות, הזמנים והערימה.

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

אלגוריתם

בנה רשימת שכנויות של זוגות (next, w) עבור כל צומת.
הגדר dist[k] = 0, את כל שאר ערכי dist לאינסוף, והכנס (0, k) לערימת מינימום.
הוצא את (t, node) הקטן ביותר. אם t > dist[node], הרשומה אינה עדכנית: דלג עליה.
אחרת, t הוא סופי. עבור כל קישור מ-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 דרך צומת 3.
סימון צומת כסופי כשהוא מוכנס לערימה במקום כשהוא נשלף ממנה. הזמן הראשון שמוצע לצומת אינו תמיד הזמן הטוב ביותר שלו; רק הרשומה הקטנה ביותר שנשלפת מהערימה היא סופית.
שכחת ‎-1. חישוב הערך המרבי בלי לבדוק מחזיר אינסוף או מדווח על הזמן הסופי הגדול ביותר ומסתיר את הצומת שמעולם לא קיבל את האות.
ספירת הצמתים החל מ־0. הצמתים ממוספרים מ־1 עד n, לכן יש להגדיר את גודל המערכים כ־n+1 ולהשאיר את המשבצת הלא־בשימוש 0 מחוץ לחישוב המקסימום.
גלישה כתוצאה מאינסוף. אם אינסוף הוא ערך ה־int הגדול ביותר, dist[u] + w יגלוש לערך שלילי עבור u שלא הגיע אליו האות. יש לדלג על צמתים שלא הגיעו אליהם, או להשתמש בערך כגון 10^9 שמשאיר מרווח.

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

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

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

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

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

למה לא להשתמש ב־BFS עבור זמן השהיית רשת?

‏BFS מבקר בצמתים לפי מספר הקישורים שמפרידים ביניהם לבין נקודת ההתחלה, וזה תואם את זמן ההגעה רק כשכל קישור נמשך אותו פרק זמן. כאן זמני הקישורים שונים, ולכן מסלול עם יותר קישורים יכול להגיע מוקדם יותר. אם כל הזמנים היו שווים, BFS היה מספיק, וכשהזמנים הם רק 0 ו-1, ‏0-1 BFS המבוסס על deque עובד.

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

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

Python

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 פעמים

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

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

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

בעיות דומות