خوارزمية فلويد-وارشال

في علم الحاسوب ، تُعرف خوارزمية فلويد-وارشال (أو خوارزمية فلويد ، أو خوارزمية روي-وارشال ، أو خوارزمية روي-فلويد ، أو خوارزمية WFI ) بأنها خوارزمية لإيجاد أقصر المسارات في رسم بياني موجه مُثقَّل ذي أوزان حواف موجبة أو سالبة (ولكن بدون دورات سالبة). ^{[ 1 ] [ 2 ]} يُحدد تنفيذ واحد للخوارزمية أطوال (مجموع الأوزان) أقصر المسارات بين جميع أزواج الرؤوس. ورغم أنها لا تُعيد تفاصيل المسارات نفسها، إلا أنه من الممكن إعادة بناء هذه المسارات بإجراء تعديلات بسيطة على الخوارزمية. كما يُمكن استخدام نسخ من الخوارزمية لإيجاد الإغلاق المتعدي لعلاقة ما، أو (في سياق نظام شولز للتصويت ) لإيجاد أوسع المسارات بين جميع أزواج الرؤوس في رسم بياني مُثقَّل.

تُعدّ خوارزمية فلويد-وارشال مثالًا على البرمجة الديناميكية ، وقد نُشرت بصيغتها المتعارف عليها حاليًا بواسطة روبرت فلويد عام 1962. ^{[ 3 ]} ومع ذلك، فهي تُشابه إلى حد كبير الخوارزميات التي نشرها سابقًا برنارد روي عام 1959 ^{[ 4 ]} وستيفن وارشال عام 1962 ^{[ 5 ]} لإيجاد الإغلاق المتعدي للرسم البياني، ^{[ 6 ]} وترتبط ارتباطًا وثيقًا بخوارزمية كلين (المنشورة عام 1956) لتحويل آلة الحالة المحدودة الحتمية إلى تعبير منتظم ، مع اختلاف استخدام شبه حلقة من نوع min-plus . ^{[ 7 ]} وقد وصف بيتر إنجرمان الصيغة الحديثة للخوارزمية على شكل ثلاث حلقات تكرار متداخلة لأول مرة، وذلك أيضًا عام 1962. ^{[ 8 ]}

تقارن خوارزمية فلويد-وارشال العديد من المسارات الممكنة عبر الرسم البياني بين كل زوج من الرؤوس. وهي تضمن إيجاد جميع أقصر المسارات، وتستطيع القيام بذلك باستخدام${\displaystyle \ثيتا (|V|^{3})}$المقارنات في الرسم البياني، ^{[ 1 ] [ 9 ]} على الرغم من أنه قد يكون هناك${\displaystyle \ثيتا (|V|^{2})}$الحواف في الرسم البياني. ويتم ذلك عن طريق تحسين تقدير أقصر مسار بين رأسين بشكل تدريجي، حتى يصبح التقدير مثالياً.

لنفترض وجود رسم بياني${\displaystyle G}$مع رؤوس${\displaystyle V}$مرقمة من 1 إلى ${\displaystyle N}$. لننظر أيضًا في دالة${\displaystyle \mathrm {shortestPath} (i,j,k)}$والتي تُعيد طول أقصر مسار ممكن (إن وُجد) من${\displaystyle i}$ل${\displaystyle j}$باستخدام الرؤوس فقط من المجموعة${\displaystyle \{1,2,\ldots ,k\}}$كنقاط وسيطة على طول الطريق. الآن، بالنظر إلى هذه الدالة، هدفنا هو إيجاد طول أقصر مسار من كل نقطة.${\displaystyle i}$لكل${\displaystyle j}$باستخدام أي رأس في${\displaystyle \{1,2,\ldots ,N\}}$بحسب التعريف، هذه هي القيمة${\displaystyle \mathrm {shortestPath} (i,j,N)}$، والتي سنجدها بشكل متكرر .

لاحظ ذلك${\displaystyle \mathrm {shortestPath} (i,j,k)}$يجب أن يكون أقل من أو يساوي${\displaystyle \mathrm {shortestPath} (i,j,k-1)}$لدينا مرونة أكبر إذا سُمح لنا باستخدام الرأس${\displaystyle k}$. لو${\displaystyle \mathrm {shortestPath} (i,j,k)}$في الواقع أقل من${\displaystyle \mathrm {shortestPath} (i,j,k-1)}$إذن، لا بد من وجود طريق من${\displaystyle i}$ل${\displaystyle j}$باستخدام الرؤوس${\displaystyle \{1,2,\ldots ,k\}}$وهذا أقصر من أي مسار مماثل لا يستخدم الرأس${\displaystyle k}$بما أنه لا توجد دورات سلبية، يمكن تحليل هذا المسار على النحو التالي:

(1) مسار من${\displaystyle i}$ل${\displaystyle k}$التي تستخدم الرؤوس${\displaystyle \{1,2,\ldots ,k-1\}}$، متبوعًا بـ

(2) مسار من${\displaystyle k}$ل${\displaystyle j}$التي تستخدم الرؤوس${\displaystyle \{1,2,\ldots ,k-1\}}$.

وبالطبع، يجب أن يكون هناك أقصر مسار (أو عدة مسارات)، وإلا سنتمكن من تقليل الطول أكثر. بعبارة أخرى، وصلنا إلى الصيغة التكرارية:

${\displaystyle \mathrm {shortestPath} (i,j,k)=}$

${\displaystyle \mathrm {min} {\Big (}\mathrm {shortestPath} (i,j,k-1),}$

${\displaystyle \mathrm {shortestPath} (i,k,k-1)+\mathrm {shortestPath} (k,j,k-1){\Big )}}$.

الحالة الأساسية معطاة بواسطة

${\displaystyle \mathrm {shortestPath} (i,j,0)=w(i,j),}$

أين${\displaystyle w(i,j)}$يشير إلى وزن الحافة من${\displaystyle i}$ل${\displaystyle j}$إذا كان موجودًا، وإلا فإن ∞ (لا نهاية).

تُشكّل هذه الصيغ جوهر خوارزمية فلويد-وارشال. تعمل الخوارزمية عن طريق حساب${\displaystyle \mathrm {shortestPath} (i,j,k)}$للجميع${\displaystyle (i,j)}$أزواج لـ${\displaystyle k=0}$، ثم${\displaystyle k=1}$، ثم${\displaystyle k=2}$وهكذا دواليك. تستمر هذه العملية حتى${\displaystyle k=N}$وقد وجدنا أقصر مسار للجميع${\displaystyle (i,j)}$يتم استخدام أي رؤوس وسيطة لإنشاء أزواج. فيما يلي الشفرة الزائفة لهذه النسخة الأساسية.

ليكن dist مصفوفة من |V| × |V| لأقصر المسافات، مُهيأة إلى ∞ (ما لا نهاية). لكل حافة ( u , v )، نُعيّن وزن الحافة ( u , v ) في dist[ u ][ v ] . لكل رأس v، نُعيّن وزن الحافة ( v ][ v ) في dist[ v ][ v ] إلى 0. لكل k من 1 إلى |V|، لكل i من 1 إلى |V|، لكل j من 1 إلى |V|، إذا كان dist[ i ][ j ] أكبر من dist[ i ][ k ] + dist[ k ][ j ] dist[ i ][ j ] = dist[ i ][ k ] + dist[ k ][ j ] end if

يتم تنفيذ الخوارزمية المذكورة أعلاه على الرسم البياني الموجود على اليسار أدناه:

قبل التكرار الأول للحلقة الخارجية، المشار إليه بـ k = 0 أعلاه، كانت المسارات المعروفة الوحيدة هي تلك التي تمثل الحواف المفردة في الرسم البياني. عند k = 1 ، تم العثور على مسارات تمر عبر الرأس 1: على وجه الخصوص، تم العثور على المسار [2,1,3]، ليحل محل المسار [2,3] الذي يحتوي على عدد أقل من الحواف ولكنه أطول (من حيث الوزن). عند k = 2 ، تم العثور على مسارات تمر عبر الرأسين {1,2}. يوضح المربعان الأحمر والأزرق كيفية تجميع المسار [4,2,1,3] من المسارين المعروفين [4,2] و[2,1,3] اللذين تمت مواجهتهما في التكرارات السابقة، مع وجود 2 في نقطة التقاطع. لم يتم النظر في المسار [4,2,3]، لأن [2,1,3] هو أقصر مسار تمت مواجهته حتى الآن من 2 إلى 3. عند k = 3 ، تم العثور على مسارات تمر عبر الرأسين {1,2,3}. وأخيراً، عند k = 4 ، يتم العثور على جميع أقصر المسارات.

ستكون مصفوفة المسافة في كل تكرار من k ، مع المسافات المحدثة بالخط العريض ، كما يلي:

الدورة السالبة هي دورة يكون مجموع أضلاعها قيمة سالبة. لا يوجد أقصر مسار بين أي زوج من الرؤوس.${\displaystyle i}$،${\displaystyle j}$والتي تشكل جزءًا من دورة سلبية، لأن أطوال المسارات من${\displaystyle i}$ل${\displaystyle j}$يمكن أن تكون القيمة صغيرة جدًا (سالبة). وللحصول على نتائج ذات دلالة عددية، تفترض خوارزمية فلويد-وارشال عدم وجود دورات سالبة. ومع ذلك، إذا وُجدت دورات سالبة، فيمكن استخدام خوارزمية فلويد-وارشال للكشف عنها. والفكرة الأساسية هي كالتالي:

• تقوم خوارزمية فلويد-وارشال بمراجعة أطوال المسارات بين جميع أزواج الرؤوس بشكل متكرر.${\displaystyle (i,j)}$، بما في ذلك حيث${\displaystyle i=j}$;
• في البداية، طول المسار${\displaystyle (i,i)}$يساوي صفرًا؛
• مسار${\displaystyle [i,k,\ldots ,i]}$لا يمكن تحسين ذلك إلا إذا كان طوله أقل من الصفر، أي أنه يشير إلى دورة سالبة؛
• وبالتالي، بعد تطبيق الخوارزمية،${\displaystyle (i,i)}$ستكون القيمة سالبة إذا كان هناك مسار ذو طول سالب من${\displaystyle i}$العودة إلى${\displaystyle i}$.

لذا، للكشف عن الدورات السالبة باستخدام خوارزمية فلويد-وارشال، يمكن فحص قطر مصفوفة المسار، ويشير وجود عدد سالب إلى أن الرسم البياني يحتوي على دورة سالبة واحدة على الأقل. ^{[ 9 ]} ومع ذلك، عند وجود دورة سالبة، أثناء تنفيذ الخوارزمية، تظهر أعداد كبيرة أُسّيًا من رتبة${\displaystyle \Omega (6^{n}\cdot w_{max})}$يمكن أن تظهر، حيث${\displaystyle w_{max}}$يمثل هذا أكبر وزن مطلق للحافة في الرسم البياني. لتجنب مشاكل تجاوز الحد الأدنى للأعداد الصحيحة، ينبغي التحقق من وجود دورة سالبة داخل حلقة التكرار الداخلية للخوارزمية. ^{[ 11 ]}

لا توفر خوارزمية فلويد-وارشال عادةً سوى أطوال المسارات بين جميع أزواج الرؤوس. مع تعديلات بسيطة، يُمكن إنشاء طريقة لإعادة بناء المسار الفعلي بين أي رأسين طرفيين. على الرغم من أن البعض قد يميل إلى تخزين المسار الفعلي من كل رأس إلى كل رأس آخر، إلا أن هذا غير ضروري، بل إنه مكلف للغاية من حيث الذاكرة. بدلاً من ذلك، يُمكننا استخدام شجرة أقصر مسار ، والتي يُمكن حسابها لكل عقدة في${\displaystyle \Theta (|E|)}$الوقت المستخدم${\displaystyle \Theta (|V|)}$الذاكرة، وتسمح لنا بإعادة بناء مسار موجه بكفاءة بين أي رأسين متصلين.

ليكن dist a${\displaystyle |V|\times |V|}$مصفوفة المسافات الدنيا مهيأة إلى${\displaystyle \infty }$(ما لا نهاية) ليكن prev هو a${\displaystyle |V|\times |V|}$مصفوفة مؤشرات الرؤوس مهيأة إلى قيمة فارغةالإجراء FloydWarshallWithPathReconstruction () هو لكل حافة (u, v) قم بما يلي: dist[u][v] = w(u, v) // وزن الحافة (u, v) prev[u][v] = u لكل رأس v، قم بما يلي: dist[v][v] = 0 prev[v][v] = v لكل k من 1 إلى |V|، نفّذ // تطبيق فلويد-وارشال القياسي لكل i من 1 إلى |V| لكل j من 1 إلى |V| إذا كان dist[i][j] > dist[i][k] + dist[k][j] ثم dist[i][j] = dist[i][k] + dist[k][j] prev[i][j] = prev[k][j]

الإجراء Path (u, v) هو إذا كان prev[u][v] = null ثم إرجاع [] المسار = [v] بينما u ≠ v افعل v = prev[u][v] path.prepend(v) مسار العودة

يترك${\displaystyle n}$يكون${\displaystyle |V|}$عدد الرؤوس. لإيجاد جميع${\displaystyle n^{2}}$ل ${\displaystyle \mathrm {shortestPath} (i,j,k)}$(للجميع)${\displaystyle i}$و${\displaystyle j}$) من تلك الخاصة بـ ${\displaystyle \mathrm {shortestPath} (i,j,k-1)}$يتطلب${\displaystyle \Theta (n^{2})}$العمليات. بما أننا نبدأ بـ ${\displaystyle \mathrm {shortestPath} (i,j,0)=\mathrm {edgeCost} (i,j)}$واحسب تسلسل${\displaystyle n}$المصفوفات${\displaystyle \mathrm {shortestPath} (i,j,1)}$،${\displaystyle \mathrm {shortestPath} (i,j,2)}$،${\displaystyle \ldots }$،${\displaystyle \mathrm {shortestPath} (i,j,n)}$، بتكلفة قدرها${\displaystyle \Theta (n^{2})}$، إجمالي التعقيد الزمني للخوارزمية هو${\displaystyle n\cdot \Theta (n^{2})=\Theta (n^{3})}$[ ^{9 ] [ 13 ]​}

يمكن استخدام خوارزمية فلويد-وارشال لحل المشكلات التالية:

• الإغلاق المتعدي للرسوم البيانية الموجهة (خوارزمية وارشال). في الصيغة الأصلية لخوارزمية وارشال، يكون الرسم البياني غير مُثقَّل ويُمثَّل بمصفوفة تجاور منطقية . ثم تُستبدل عملية الجمع بالاقتران المنطقي (و) وعملية إيجاد أصغر قيمة بالفصل المنطقي (أو).
• إيجاد تعبير منتظم يدل على اللغة المنتظمة التي تقبلها آلة محدودة ( خوارزمية كلين ، وهي تعميم وثيق الصلة بخوارزمية فلويد-وارشال) ^{[ 14 ]}
• عكس المصفوفات الحقيقية ( خوارزمية جاوس- جوردان ) ^{[ 15 ]}
• التوجيه الأمثل. في هذا التطبيق، نهتم بإيجاد المسار ذي التدفق الأقصى بين رأسين. هذا يعني أنه بدلاً من اختيار القيم الدنيا كما في الشفرة الزائفة أعلاه، نختار القيم القصوى. تمثل أوزان الحواف قيودًا ثابتة على التدفق، بينما تمثل أوزان المسارات نقاط الاختناق؛ لذا تُستبدل عملية الجمع المذكورة أعلاه بعملية إيجاد القيمة الدنيا.
• الحساب السريع لشبكات باثفايندر .
• أوسع المسارات / مسارات النطاق الترددي الأقصى
• حساب الشكل المتعارف عليه لمصفوفات حدود الفرق (DBMs)
• حساب التشابه بين الرسوم البيانية
• الإغلاق المتعدي في الرسوم البيانية AND/OR/threshold. ^{[ 16 ]}

تتوفر تطبيقات للعديد من لغات البرمجة .

• بالنسبة للغة C++ ، في مكتبة boost::graph
• بالنسبة للغة C# ، على موقع QuikGraph
• بالنسبة للغة C# ، في QuickGraphPCL (نسخة معدلة من QuickGraph مع توافق أفضل مع المشاريع التي تستخدم مكتبات الفئات المحمولة).
• بالنسبة للغة جافا ، في مكتبة Apache Commons Graph
• بالنسبة للغة جافا سكريبت ، في مكتبة Cytoscape
• بالنسبة للغة جوليا ، في حزمة Graphs.jl
• بالنسبة لبرنامج MATLAB ، في حزمة Matlab_bgl المؤرشفة بتاريخ 17 أغسطس 2013 على موقع Wayback Machine
• بالنسبة للغة بيرل ، في وحدة الرسم البياني
• بالنسبة للغة بايثون ، في مكتبة SciPy (الوحدة النمطية scipy.sparse.csgraph ) أو مكتبة NetworkX
• بالنسبة للغة R ، في الحزمتين e1071 و Rfast
• بالنسبة للغة C ، يوجد تطبيق متوازي باستخدام مكتبة pthreads ، يتضمن واجهة SQLite للبيانات في الملف floydWarshall.h

بالنسبة للرسوم البيانية ذات أوزان الحواف غير السالبة، يمكن استخدام خوارزمية ديكسترا لإيجاد جميع أقصر المسارات من رأس واحد في وقت تشغيل${\displaystyle \Theta (|E|+|V|\log |V|)}$وبالتالي، فإن تشغيل خوارزمية ديكسترا بدءًا من كل رأس يستغرق وقتًا${\displaystyle \Theta (|E||V|+|V|^{2}\log |V|)}$. منذ${\displaystyle |E|=O(|V|^{2})}$وهذا ينتج عنه أسوأ وقت تشغيل لخوارزمية ديكسترا المتكررة لـ${\displaystyle O(|V|^{3})}$بينما يتطابق هذا مع وقت التشغيل التقريبي في أسوأ الحالات لخوارزمية فلويد-وارشال، فإن الثوابت المستخدمة لها أهمية كبيرة. عندما يكون الرسم البياني كثيفًا (أي،${\displaystyle |E|\approx |V|^{2}}$)، تميل خوارزمية فلويد-وارشال إلى الأداء بشكل أفضل عمليًا. عندما يكون الرسم البياني متفرقًا (أي،${\displaystyle |E|}$أصغر بكثير من${\displaystyle |V|^{2}}$)، يميل ديكسترا إلى الهيمنة.

بالنسبة للرسوم البيانية المتفرقة ذات الحواف السالبة ولكن بدون دورات سالبة، يمكن استخدام خوارزمية جونسون ، بنفس وقت التشغيل التقاربي لنهج ديكسترا المتكرر.

توجد أيضًا خوارزميات معروفة تستخدم ضرب المصفوفات السريع لتسريع حساب أقصر مسار بين جميع أزواج العناصر في الرسوم البيانية الكثيفة، ولكنها عادةً ما تفترض افتراضات إضافية حول أوزان الحواف (مثل اشتراط أن تكون أعدادًا صحيحة صغيرة). ^{[ 17 ] [ 18 ]} إضافةً إلى ذلك، ونظرًا لعوامل الثبات العالية في وقت تشغيلها، فإنها لا تُحسّن سرعة خوارزمية فلويد-وارشال إلا في حالة الرسوم البيانية الكبيرة جدًا.

• رسوم متحركة تفاعلية لخوارزمية فلويد-وارشال
• رسوم متحركة تفاعلية لخوارزمية فلويد-وارشال (الجامعة التقنية في ميونخ)