Network Delay Time

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

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

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

يُثبّت ديكسترا العقدة ذات الزمن التقديري الأصغر ولا ينظر إليها مرة أخرى. لا يكون ذلك آمنًا إلا إذا تعذّر وجود مسار لاحق أقصر، ومع الأوزان غير السالبة، تكون كلفة كل مسار يمر عبر عقدة لم تُثبّت بعد مساوية لزمن تلك العقدة أو أكبر منه. يكسر الرابط ذو الوزن السالب هذا المنطق: فقد ينتهي مسار يمر عبر عقدة بدت أعلى كلفةً إلى كلفة أقل. عند وجود أوزان سالبة، استخدم Bellman-Ford.

Q: لماذا لا نستخدم BFS لحساب زمن تأخير الشبكة؟

تزور خوارزمية BFS العُقد بحسب عدد الروابط التي تفصلها عن نقطة البداية، وهذا يطابق وقت الوصول فقط عندما يستغرق كل رابط الوقت نفسه. تختلف أوقات الروابط هنا، لذا قد يصل مسار يضم روابط أكثر في وقت أقصر. إذا كانت جميع الأوقات متساوية، لكانت BFS كافية، ومع اقتصار الأوقات على 0 و1، تعمل خوارزمية 0-1 BFS المعتمدة على deque.

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

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

بيلمان-فورد: استرخِ كل رابط حتى 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، وتعرض وقتًا قدره 4 للعقدة 2 ووقتًا قدره 1 للعقدة 3. تكون قيمة العقدة 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 ضمن القيمة القصوى.
حدوث تجاوز بسبب ما لا نهاية. إذا كانت قيمة ما لا نهاية هي أكبر عدد صحيح، فإن dist[u] + w تلتف لتصبح عددًا سالبًا عند عدم الوصول إلى u. تخطَّ العقد التي لم يتم الوصول إليها، أو استخدم قيمة مثل 10^9 تترك مجالًا كافيًا.

أسئلة شائعة4

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

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

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

يُثبّت ديكسترا العقدة ذات الزمن التقديري الأصغر ولا ينظر إليها مرة أخرى. لا يكون ذلك آمنًا إلا إذا تعذّر وجود مسار لاحق أقصر، ومع الأوزان غير السالبة، تكون كلفة كل مسار يمر عبر عقدة لم تُثبّت بعد مساوية لزمن تلك العقدة أو أكبر منه. يكسر الرابط ذو الوزن السالب هذا المنطق: فقد ينتهي مسار يمر عبر عقدة بدت أعلى كلفةً إلى كلفة أقل. عند وجود أوزان سالبة، استخدم Bellman-Ford.

لماذا لا نستخدم BFS لحساب زمن تأخير الشبكة؟

تزور خوارزمية BFS العُقد بحسب عدد الروابط التي تفصلها عن نقطة البداية، وهذا يطابق وقت الوصول فقط عندما يستغرق كل رابط الوقت نفسه. تختلف أوقات الروابط هنا، لذا قد يصل مسار يضم روابط أكثر في وقت أقصر. إذا كانت جميع الأوقات متساوية، لكانت BFS كافية، ومع اقتصار الأوقات على 0 و1، تعمل خوارزمية 0-1 BFS المعتمدة على deque.

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

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

الدالة

القيود

أمثلة

تلميحات

الحل

البحث بالعمق أولًا الذي يعيد الزيارة عند كل مسار أسرع

بيلمان-فورد: استرخِ كل رابط حتى n-1 مرة

خوارزمية ديكسترا باستخدام كومة صغرى

أخطاء شائعة وحالات حدّية

أسئلة شائعة4

مسائل مشابهة