Network Delay Time

Q: ما هو التعقيد الزمني لمسألة تأخير الشبكة؟

باستخدام خوارزمية Dijkstra وكومة ثنائية، يكون التعقيد O(E log E) ، حيث إن E هو عدد الروابط. وهذا يساوي O(E log n) ، لأن E لا يتجاوز n². وتعقيد المساحة هو O(n + E) . يستغرق Bellman-Ford زمنًا قدره O(n · E) .

Q: لماذا تحتاج خوارزمية ديكسترا إلى أوزان غير سالبة؟

لا يعيد Dijkstra زيارة عقدة حُسمت، وهذا آمن فقط إذا لم يكن هناك مسار لاحق أقصر. مع روابط A → B بزمن 2، و A → C بزمن 3، و C → B بزمن -2، يحسم العقدة B عند 2، لكن المسار عبر C يصل إليها عند 1. يتعامل Bellman-Ford مع الأزمنة السالبة.

Q: هل يمكنك حل مسألة Network Delay Time دون كومة؟

نعم. تفحص خوارزمية ديكسترا باستخدام مصفوفة عادية كل عقدة لم تُحسم بعد للعثور على أصغر زمن، وتبلغ كلفتها الإجمالية 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 و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 عندما لا يوجد مسار إلى عقدة ما. أزمنة الروابط غير سالبة أبدًا، لذا تحسم خوارزمية Dijkstra كل عقدة مرة واحدة. أدناه، 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

ما هو التعقيد الزمني لمسألة تأخير الشبكة؟

باستخدام خوارزمية Dijkstra وكومة ثنائية، يكون التعقيد O(E log E)، حيث إن E هو عدد الروابط. وهذا يساوي O(E log n)، لأن E لا يتجاوز n². وتعقيد المساحة هو O(n + E). يستغرق Bellman-Ford زمنًا قدره O(n · E).

لماذا تحتاج خوارزمية ديكسترا إلى أوزان غير سالبة؟

لا يعيد Dijkstra زيارة عقدة حُسمت، وهذا آمن فقط إذا لم يكن هناك مسار لاحق أقصر. مع روابط A → B بزمن 2، وA → C بزمن 3، وC → B بزمن -2، يحسم العقدة B عند 2، لكن المسار عبر C يصل إليها عند 1. يتعامل Bellman-Ford مع الأزمنة السالبة.

هل يمكنك حل مسألة Network Delay Time دون كومة؟

نعم. تفحص خوارزمية ديكسترا باستخدام مصفوفة عادية كل عقدة لم تُحسم بعد للعثور على أصغر زمن، وتبلغ كلفتها الإجمالية 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

مسائل مشابهة