https://wiki.hsoub.com/index.php?title=Algorithms/Floyd_Warshall&feed=atom&action=history
Algorithms/Floyd Warshall - تاريخ المراجعة
2024-03-28T12:37:43Z
تاريخ التعديل لهذه الصفحة في الويكي
MediaWiki 1.35.0
https://wiki.hsoub.com/index.php?title=Algorithms/Floyd_Warshall&diff=29627&oldid=prev
جميل-بيلوني: /* خطوات الخوارزمية */
2020-03-03T09:53:39Z
<p><span dir="auto"><span class="autocomment">خطوات الخوارزمية</span></span></p>
<table class="diff diff-contentalign-right diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="ar">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">→ مراجعة أقدم</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">مراجعة 09:53، 3 مارس 2020</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l21" >سطر 21:</td>
<td colspan="2" class="diff-lineno">سطر 21:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>لاحظ أنّ القيمة <code>graph[i][j]</code> هي <code>0</code> إن كانت <code>i</code> تساوي <code>j</code>، وأنّ قيمة <code>graph[i][j]</code> تساوي <code>INF</code> (ما لا نهاية) إن لم يكن هناك ضلع يربط بين الرأسين <code>i</code> و <code>j</code>.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>لاحظ أنّ القيمة <code>graph[i][j]</code> هي <code>0</code> إن كانت <code>i</code> تساوي <code>j</code>، وأنّ قيمة <code>graph[i][j]</code> تساوي <code>INF</code> (ما لا نهاية) إن لم يكن هناك ضلع يربط بين الرأسين <code>i</code> و <code>j</code>.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><source lang="">المخرجات:</div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><source lang="<ins class="diffchange diffchange-inline">text</ins>">المخرجات:</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Shortest distance matrix</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Shortest distance matrix</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> 0 5 8 9</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> 0 5 8 9</div></td></tr>
</table>
جميل-بيلوني
https://wiki.hsoub.com/index.php?title=Algorithms/Floyd_Warshall&diff=29201&oldid=prev
Mohammed Taher في 12:14، 20 أكتوبر 2019
2019-10-20T12:14:23Z
<p></p>
<table class="diff diff-contentalign-right diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="ar">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">→ مراجعة أقدم</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">مراجعة 12:14، 20 أكتوبر 2019</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l37" >سطر 37:</td>
<td colspan="2" class="diff-lineno">سطر 37:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div># أن يكون <code>k</code> رأسًا وسطيًا في المسار الأقصر الذي يفصل بين <code>i</code> و <code>j</code>؛ لذا نحدث قيمة <code>dist[i][j]</code> لتصبح <code>dist[i][k] + disk[k][j]</code> إذا كانت <code>dist[i][j] > dist[i][k] + dist[k][j]</code>.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div># أن يكون <code>k</code> رأسًا وسطيًا في المسار الأقصر الذي يفصل بين <code>i</code> و <code>j</code>؛ لذا نحدث قيمة <code>dist[i][j]</code> لتصبح <code>dist[i][k] + disk[k][j]</code> إذا كانت <code>dist[i][j] > dist[i][k] + dist[k][j]</code>.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>== <del class="diffchange diffchange-inline">أمثلة </del>==</div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>== <ins class="diffchange diffchange-inline">تنفيذ الخوارزمية </ins>==</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>تعرض الأمثلة التالية طريقة تنفيذ الخوارزمية في عدد من لغات البرمجة:</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>تعرض الأمثلة التالية طريقة تنفيذ الخوارزمية في عدد من لغات البرمجة:</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>* C++:</div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>* C++<ins class="diffchange diffchange-inline"></ins>:</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><source lang="c++">#include <bits/stdc++.h> </div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><source lang="c++">#include <bits/stdc++.h> </div></td></tr>
<tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l327" >سطر 327:</td>
<td colspan="2" class="diff-lineno">سطر 327:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== التعقيد الزمني ==</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== التعقيد الزمني ==</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>يبلغ التعقيد الزمني لهذه الخوارزمية المقدار <code>O(V<del class="diffchange diffchange-inline">^</del>3)</code>.</div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>يبلغ التعقيد الزمني لهذه الخوارزمية المقدار <code>O(V<ins class="diffchange diffchange-inline"><sup></ins>3<ins class="diffchange diffchange-inline"></sup></ins>)</code>.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>يطبع البرنامج أعلاه المسافات الأقصر فقط، ويمكن تعديل الحل ليطبع المسارات الأقصر أيضًا، وذلك بتخزين المعلومات السابقة في مصفوفة ثنائية الأبعاد.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>يطبع البرنامج أعلاه المسافات الأقصر فقط، ويمكن تعديل الحل ليطبع المسارات الأقصر أيضًا، وذلك بتخزين المعلومات السابقة في مصفوفة ثنائية الأبعاد.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>كذلك استخدام القيمة <code>INT_MAX</code> من الترويسة <code>limits.h</code> عوضًا عن القيمة <code>INF</code> وذلك لضمان أنّنا نتعامل مع أكبر قيمة ممكنة، وعند القيام بذلك يجب تعديل عبارة الشرطية في البرنامج أعلاه لتجنب حدوث فيضان حسابي arithmetic overflow.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>كذلك استخدام القيمة <code>INT_MAX</code> من الترويسة <code>limits.h</code> عوضًا عن القيمة <code>INF</code> وذلك لضمان أنّنا نتعامل مع أكبر قيمة ممكنة، وعند القيام بذلك يجب تعديل عبارة الشرطية في البرنامج أعلاه لتجنب حدوث فيضان حسابي arithmetic overflow.</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">== انظر أيضًا ==</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">* [[Algorithms/Bellman Ford|خوارزمية بلمان-فورد:]] تمتاز هذه الخوارزمية بقدرتها على إيجاد المسار الأقصر في الرسوم البيانية التي تكون فيها أوزان الأضلاع ذات قيم سالبة.</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">* [[Algorithms/Dijkstra|خوارزمية ديكسترا:]] تنتج خورازمية ديكسترا Dijkstra شجرة المسار الأقصر بدءًا من المصدر المعطى كجذر لهذه الشجرة.</ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== مصادر ==</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== مصادر ==</div></td></tr>
</table>
Mohammed Taher
https://wiki.hsoub.com/index.php?title=Algorithms/Floyd_Warshall&diff=29200&oldid=prev
Mohammed Taher: أنشأ الصفحة ب'<noinclude>{{DISPLAYTITLE:خوارزمية فلويد وارشال}}</noinclude> تقدّم خوارزمية فلويد-وارشال Floyd-Warshall حلًّا لمشكل...'
2019-10-20T12:10:43Z
<p>أنشأ الصفحة ب'<noinclude>{{DISPLAYTITLE:خوارزمية فلويد وارشال}}</noinclude> تقدّم خوارزمية فلويد-وارشال Floyd-Warshall حلًّا لمشكل...'</p>
<p><b>صفحة جديدة</b></p><div><noinclude>{{DISPLAYTITLE:خوارزمية فلويد وارشال}}</noinclude><br />
تقدّم خوارزمية فلويد-وارشال Floyd-Warshall حلًّا لمشكلة المسار الأقصر لجميع الأزواج، فالمطلوب هو العثور على أقصر مسافة تفصل بين كل زوج من الرؤوس في الرسم البياني الموزون الموجّه المعطى.<br />
<br />
<source lang="text"><br />
المدخلات:<br />
graph[][] = { {0, 5, INF, 10},<br />
{INF, 0, 3, INF},<br />
{INF, INF, 0, 1},<br />
{INF, INF, INF, 0} }<br />
<br />
تمثل المدخلات الرسم البياني التالي:<br />
<br />
10<br />
(0)------->(3)<br />
| /|\<br />
5 | |<br />
| | 1<br />
\|/ |<br />
(1)------->(2)<br />
3 </source><br />
لاحظ أنّ القيمة <code>graph[i][j]</code> هي <code>0</code> إن كانت <code>i</code> تساوي <code>j</code>، وأنّ قيمة <code>graph[i][j]</code> تساوي <code>INF</code> (ما لا نهاية) إن لم يكن هناك ضلع يربط بين الرأسين <code>i</code> و <code>j</code>.<br />
<br />
<source lang="">المخرجات:<br />
Shortest distance matrix<br />
0 5 8 9<br />
INF 0 3 4<br />
INF INF 0 1<br />
INF INF INF 0 <br />
</source><br />
== خطوات الخوارزمية ==<br />
<br />
تبدأ الخوارزمية بتهيئة مصفوفة الحل solution matrix التي تكون مشابهة لمصفوفة الرسم البياني المدخل، ثم تحدّث مصفوفة الحل وذلك باعتبار جميع الرؤوس كرأس وسطي. تنتقي الخوارزمية جميع الرؤوس واحدًا تلو الآخر وتحدث جميع قيم المسارات الأقصر التي تتضمن الرأس المنتخب كرأس وسطي في المسار الأقصر. <br />
<br />
عند انتخاب الرأس ذي الرقم <code>k</code> كرأس وسطي، فإنّنا قد عددنا الرؤوس <code>{0, 1, 2, ..k-1}</code> كرؤوس وسطية، ولكل زوج <code>(i, j)</code> لرؤوس المصدر والوجهة على التوالي هناك احتمالان:<br />
<br />
# أن لا يكون <code>k</code> رأسًا وسطيًا في المسار الأقصر الذي يفصل بين <code>i</code> و <code>j</code>؛ لذا نبقي على قيمة <code>dist[i][j]</code> كما هي.<br />
# أن يكون <code>k</code> رأسًا وسطيًا في المسار الأقصر الذي يفصل بين <code>i</code> و <code>j</code>؛ لذا نحدث قيمة <code>dist[i][j]</code> لتصبح <code>dist[i][k] + disk[k][j]</code> إذا كانت <code>dist[i][j] > dist[i][k] + dist[k][j]</code>.<br />
<br />
== أمثلة ==<br />
<br />
تعرض الأمثلة التالية طريقة تنفيذ الخوارزمية في عدد من لغات البرمجة:<br />
<br />
* C++:<br />
<br />
<source lang="c++">#include <bits/stdc++.h> <br />
using namespace std; <br />
<br />
// عدد الرؤوس في الرسم البياني<br />
#define V 4 <br />
<br />
/* تعيين قيمة كبيرة لتمثل قيمة ما لا نهاية.<br />
ستستخدم هذه القيمة للرؤوس غير المرتبطة ببعضها البعض */<br />
#define INF 99999 <br />
<br />
// تطبع الدالة مصفوفة الحل<br />
void printSolution(int dist[][V]); <br />
<br />
void floydWarshall (int graph[][V]) <br />
{ <br />
/* ستكون المصفوفة أدناه مصفوفة المخرجات والتي ستحتوي<br />
على المسافات الأقصر بين كل زوج من الرؤوس في الرسم البياني */<br />
int dist[V][V], i, j, k; <br />
<br />
<br />
/* تهيئة مصفوفة الحل لتكون مشابهة لمصفوفة المدخلات.<br />
أو يمكن القول: أن القيم الابتدائية للمسافات ألأقصر<br />
تستند على المسافات الأقصر مع الأخذ بنظر الاعتبار<br />
عدم وجود رأس وسطي */<br />
for (i = 0; i < V; i++) <br />
for (j = 0; j < V; j++) <br />
dist[i][j] = graph[i][j]; <br />
<br />
/* إضافة جميع الرؤوس واحدًا تلو الآخر إلى مجموعة<br />
الرؤوس الوسية.<br />
---> تكون المسافات الأقصر بين جميع أزواج العقد في الرسم البياني<br />
بحيث تأخذ بنظر الاعتبار فقط الرؤوس الموجودة في المجموعة<br />
{0, 1, 2, .. k-1}<br />
كرؤوس وسطية.<br />
---> بعد انتهاء عمل الحلقة التكرارية<br />
k يضاف الرأس <br />
إلى مجموعة الرؤوس الوسطية وتصبح المجموعة<br />
{0, 1, 2, .. k}<br />
*/<br />
<br />
for (k = 0; k < V; k++) <br />
{ <br />
// اختيار جميع الرؤوس لتكون المصدر واحدًا تلو الآخر<br />
for (i = 0; i < V; i++) <br />
{ <br />
// اختيار جميع الرؤوس التي ستكون وجهة للمصدر المنتخب في الخطوة السابقة<br />
for (j = 0; j < V; j++) <br />
{ <br />
// إن كان المتغير الخاص بالحلقة التكرارية الأولى في المسار الأقصر<br />
// بين متغير الحلقة الثانية والثالثة فسنحدث قيمة <br />
// dist[i][j]<br />
if (dist[i][k] + dist[k][j] < dist[i][j]) <br />
dist[i][j] = dist[i][k] + dist[k][j]; <br />
} <br />
} <br />
} <br />
<br />
// طباعة مصفوفة المسافة الأقصر<br />
printSolution(dist); <br />
} <br />
<br />
/* دالة مساعدة لطباعة الحل */<br />
void printSolution(int dist[][V]) <br />
{ <br />
cout<<"The following matrix shows the shortest distances"<br />
" between every pair of vertices \n"; <br />
for (int i = 0; i < V; i++) <br />
{ <br />
for (int j = 0; j < V; j++) <br />
{ <br />
if (dist[i][j] == INF) <br />
cout<<"INF"<<" "; <br />
else<br />
cout<<dist[i][j]<<" "; <br />
} <br />
cout<<endl; <br />
} <br />
} <br />
<br />
// اختبار الدوال السابقة<br />
int main() <br />
{ <br />
/* إنشاء الرسم البياني الموزون التالي:<br />
10 <br />
(0)------->(3) <br />
| /|\ <br />
5 | | <br />
| | 1 <br />
\|/ | <br />
(1)------->(2) <br />
3 */<br />
int graph[V][V] = { {0, 5, INF, 10}, <br />
{INF, 0, 3, INF}, <br />
{INF, INF, 0, 1}, <br />
{INF, INF, INF, 0} <br />
}; <br />
<br />
// طباعة الحل<br />
floydWarshall(graph); <br />
return 0; <br />
} <br />
</source><br />
* بايثون:<br />
<br />
<source lang="python"><br />
# عدد الرؤوس في الرسم البياني<br />
V = 4<br />
<br />
# تعيين قيمة كبيرة لتمثل قيمة ما لا نهاية.<br />
# ستستخدم هذه القيمة للرؤوس غير المرتبطة ببعضها البعض<br />
INF = 99999<br />
<br />
def floydWarshall(graph): <br />
<br />
# ستكون المصفوفة أدناه مصفوفة المخرجات والتي ستحتوي<br />
# على المسافات الأقصر بين كل زوج من الرؤوس في الرسم البياني<br />
# تهيئة مصفوفة الحل لتكون مشابهة لمصفوفة المدخلات.<br />
# أو يمكن القول: أن القيم الابتدائية للمسافات ألأقصر<br />
# تستند على المسافات الأقصر مع الأخذ بنظر الاعتبار<br />
# عدم وجود رأس وسطي<br />
<br />
dist = map(lambda i : map(lambda j : j , i) , graph) <br />
<br />
# إضافة جميع الرؤوس واحدًا تلو الآخر إلى مجموعة<br />
الرؤوس الوسية.<br />
# ---> تكون المسافات الأقصر بين جميع أزواج العقد في الرسم البياني<br />
# بحيث تأخذ بنظر الاعتبار فقط الرؤوس الموجودة في المجموعة<br />
# {0, 1, 2, .. k-1}<br />
# كرؤوس وسطية.<br />
# ---> بعد انتهاء عمل الحلقة التكرارية<br />
# k يضاف الرأس <br />
# إلى مجموعة الرؤوس الوسطية وتصبح المجموعة<br />
# {0, 1, 2, .. k}<br />
<br />
for k in range(V): <br />
<br />
# اختيار جميع الرؤوس لتكون المصدر واحدًا تلو الآخر <br />
for i in range(V): <br />
<br />
# اختيار جميع الرؤوس التي ستكون وجهة <br />
# للمصدر المنتخب في الخطوة السابقة <br />
for j in range(V): <br />
<br />
# إن كان المتغير الخاص بالحلقة التكرارية الأولى في المسار الأقصر <br />
# بين متغير الحلقة الثانية والثالثة فسنحدث قيمة<br />
# dist[i][j]<br />
dist[i][j] = min(dist[i][j] , <br />
dist[i][k]+ dist[k][j] <br />
) <br />
printSolution(dist) <br />
<br />
<br />
# دالة مساعدة لطباعة الحل<br />
def printSolution(dist): <br />
print "Following matrix shows the shortest distances\ <br />
between every pair of vertices" <br />
for i in range(V): <br />
for j in range(V): <br />
if(dist[i][j] == INF): <br />
print "%7s" %("INF"), <br />
else: <br />
print "%7d\t" %(dist[i][j]), <br />
if j == V-1: <br />
print "" <br />
<br />
<br />
<br />
# اختبار الدوال السابقة<br />
# إنشاء الرسم البياني الموزون التالي<br />
""" <br />
10 <br />
(0)------->(3) <br />
| /|\ <br />
5 | | <br />
| | 1 <br />
\|/ | <br />
(1)------->(2) <br />
3 """<br />
graph = [[0,5,INF,10], <br />
[INF,0,3,INF], <br />
[INF, INF, 0, 1], <br />
[INF, INF, INF, 0] <br />
] <br />
# طباعة الحل<br />
floydWarshall(graph); </source><br />
* جافا:<br />
<br />
<source lang="java">import java.util.*; <br />
import java.lang.*; <br />
import java.io.*; <br />
<br />
<br />
class AllPairShortestPath <br />
{ <br />
final static int INF = 99999, V = 4; <br />
<br />
void floydWarshall(int graph[][]) <br />
{ <br />
int dist[][] = new int[V][V]; <br />
int i, j, k; <br />
<br />
/* تهيئة مصفوفة الحل لتكون مشابهة لمصفوفة المدخلات.<br />
أو يمكن القول: أن القيم الابتدائية للمسافات ألأقصر<br />
تستند على المسافات الأقصر مع الأخذ بنظر الاعتبار<br />
عدم وجود رأس وسطي */<br />
for (i = 0; i < V; i++) <br />
for (j = 0; j < V; j++) <br />
dist[i][j] = graph[i][j]; <br />
<br />
/* إضافة جميع الرؤوس واحدًا تلو الآخر إلى مجموعة<br />
الرؤوس الوسية.<br />
---> تكون المسافات الأقصر بين جميع أزواج العقد في الرسم البياني<br />
بحيث تأخذ بنظر الاعتبار فقط الرؤوس الموجودة في المجموعة<br />
{0, 1, 2, .. k-1}<br />
كرؤوس وسطية.<br />
---> بعد انتهاء عمل الحلقة التكرارية<br />
k يضاف الرأس <br />
إلى مجموعة الرؤوس الوسطية وتصبح المجموعة<br />
{0, 1, 2, .. k}<br />
*/<br />
for (k = 0; k < V; k++) <br />
{ <br />
// اختيار جميع الرؤوس لتكون المصدر واحدًا تلو الآخر <br />
for (i = 0; i < V; i++) <br />
{ <br />
// اختيار جميع الرؤوس التي ستكون وجهة للمصدر المنتخب في الخطوة السابقة <br />
for (j = 0; j < V; j++) <br />
{ <br />
// إن كان المتغير الخاص بالحلقة التكرارية الأولى في المسار الأقصر<br />
// بين متغير الحلقة الثانية والثالثة فسنحدث قيمة <br />
// dist[i][j]<br />
if (dist[i][k] + dist[k][j] < dist[i][j]) <br />
dist[i][j] = dist[i][k] + dist[k][j]; <br />
} <br />
} <br />
} <br />
<br />
// طباعة مصفوفة المسافة الأقصر <br />
printSolution(dist); <br />
} <br />
<br />
void printSolution(int dist[][]) <br />
{ <br />
System.out.println("The following matrix shows the shortest "+ <br />
"distances between every pair of vertices"); <br />
for (int i=0; i<V; ++i) <br />
{ <br />
for (int j=0; j<V; ++j) <br />
{ <br />
if (dist[i][j]==INF) <br />
System.out.print("INF "); <br />
else<br />
System.out.print(dist[i][j]+" "); <br />
} <br />
System.out.println(); <br />
} <br />
} <br />
<br />
// اختبار الدوال السابقة<br />
public static void main (String[] args) <br />
{ <br />
/* إنشاء الرسم البياني الموزون التالي: <br />
10 <br />
(0)------->(3) <br />
| /|\ <br />
5 | | <br />
| | 1 <br />
\|/ | <br />
(1)------->(2) <br />
3 */<br />
int graph[][] = { {0, 5, INF, 10}, <br />
{INF, 0, 3, INF}, <br />
{INF, INF, 0, 1}, <br />
{INF, INF, INF, 0} <br />
}; <br />
AllPairShortestPath a = new AllPairShortestPath(); <br />
<br />
// طباعة الحل<br />
a.floydWarshall(graph); <br />
} <br />
} <br />
</source><br />
== التعقيد الزمني ==<br />
<br />
يبلغ التعقيد الزمني لهذه الخوارزمية المقدار <code>O(V^3)</code>.<br />
<br />
يطبع البرنامج أعلاه المسافات الأقصر فقط، ويمكن تعديل الحل ليطبع المسارات الأقصر أيضًا، وذلك بتخزين المعلومات السابقة في مصفوفة ثنائية الأبعاد.<br />
<br />
كذلك استخدام القيمة <code>INT_MAX</code> من الترويسة <code>limits.h</code> عوضًا عن القيمة <code>INF</code> وذلك لضمان أنّنا نتعامل مع أكبر قيمة ممكنة، وعند القيام بذلك يجب تعديل عبارة الشرطية في البرنامج أعلاه لتجنب حدوث فيضان حسابي arithmetic overflow.<br />
<br />
== مصادر ==<br />
<br />
* صفحة [https://www.geeksforgeeks.org/floyd-warshall-algorithm-dp-16/ Floyd Warshall Algorithm] في توثيق الخوارزميات في موقع GeeksforGeeks.<br />
<br />
[[تصنيف: الخوارزميات]]<br />
[[تصنيف: خوارزميات الرسوم البيانية]]</div>
Mohammed Taher