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: أوزان الحواف: تمثل matrix[i][j] وزن الحافة من i إلى j، أو -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

فلويد-وارشال: أضف محطةً أخرى في كل جولة

الفكرة

حدِّد العُقد التي يُسمح للمسار بالتوقف عندها بين طرفيه. يبدأ الجدول كمصفوفة، أي بالمسارات التي لا تتضمن أي توقف. بعد الجولة k، تكون dist[i][j] أقصر مسار تكون جميع نقاط توقفه ضمن العُقد من 0 إلى k، وتُعطي الجولة الأخيرة الإجابة.

في الجولة k، إما أن يتجاوز أفضل مسار يُسمح له أيضًا بالتوقف عند k هذه العقدة، ويكون الجدول قد احتفظ به بالفعل، أو يمر عبر k مرة واحدة، إذ لا توجد أوزان سالبة. ولا تتوقف أيٌّ من نصفيه إلا عند العُقد من 0 إلى k-1، لذا فهما dist[i][k] وdist[k][j].

في المثال الأول، تستبدل الجولة 1 المسافة المباشرة البالغة 11 من العقدة 0 إلى العقدة 2 بمسافة 6. وتعطي الجولة 2 المسافة من العقدة 0 إلى العقدة 3: 6 + 3 = 9، مع وقوع نقطة التوقف عند العقدة 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.
استخدام أكبر عدد صحيح كقيمة للمالانهاية: جمع عددين منه يؤدي إلى تجاوز سعة عدد صحيح ذي 32 بت، فينتج عن ذلك مسافة سالبة. أقصى مسافة حقيقية هي 99 × 1000 = 99,000، لذا فإن 10^9 آمن، لأن 2 × 10^9 أقل من 2^31-1.
افتراض أن الحواف تسير في الاتجاهين. في المثال الثاني، تصل العقدة 0 إلى العقدة 1، لكن العقدة 1 لا تصل إلى أي مكان.
تشغيل البحث بالعرض أولًا، الذي يتجاهل الأوزان: في المثال الأول، يُبلغ عن مسافة 11 من العقدة 0 إلى العقدة 2، لا 6.

أسئلة شائعة3

ما هو التعقيد الزمني لخوارزمية فلويد وورشال؟

زمن O(n³) لـ n عقد: ثلاث حلقات متداخلة على العقد، مع عملية جمع واحدة ومقارنة واحدة في كل خطوة، و10^6 خطوة لـ 100 عقدة. المساحة هي O(n²) لجدول المسافات، الذي يمكن تحديثه في موضعه.

هل تعمل خوارزمية Floyd Warshall مع أوزان الحواف السالبة؟

نعم، ما دام لا توجد دورة سالبة، أي دورة يكون مجموع أوزانها أقل من 0. عند وجود دورة سالبة، لا تكون أقصر المسارات مُعرَّفة، ويُظهر الجدول ذلك: تنتهي بعض قيم dist[i][i] بأقل من 0.

متى ينبغي أن تستخدم Floyd Warshall بدلاً من خوارزمية Dijkstra؟

استخدم 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]]