نستعرض في هذا المقال بعض أشهر الخوارزميات المستخدمة لتحليل المسارات في الأشجار، مثل خوارزمية بْرِم Prim وخوارزمية فلويد-وورشال Floyd-Warshall وخوارِزمية بلمان-فورد Bellman-Ford.
خوارزمية برم Prim's Algorithm
لنفترض أنّ لدينا 8 منازل، ونريد إعداد خطوط هاتفية بينها بأقل تكلفة ممكنة. لأجل ذلك سننشئ شجرةً حروفها تمثل المنازل، وأضلَاعها تمثّل تكلفة توصيل الخط الهاتفي بين منزلين.
سنحاول وصل الخطوط بين جميع المنازل بأقل كلفة ممكنة، ولتحقيق ذلك سنستخدم خوارزمية برم Prim، وهي خوارزمية شرهة تبحث عن أصغر شجرة ممتدة spanning tree في مخطط موزون غير موجّه undirected weighted graph. وهذا يعني أنها تبحث عن مجموعة من الأضلاع التي تشكل شجرة تتضمّن كل العقد، بحيث يكون الوزن الإجمالي لجميع أضلاع الشجرة أقل ما يمكن.
طُوِّرت هذه الخوارزمية عام 1930 من قبل عالم الرياضيات التشيكي Vojtěch Jarník، ثم أعاد عالم الحوسبة روبرت كلاي بْرِم اكتشافها ونشرها في عام 1957، وكذلك إيدجر ديكسترا في عام 1959. تُعرف أيضًا باسم خوارزمية DJP وخوارزمية Jarnik وخوارزمية Prim-Jarnik وخوارزمية Prim-Dijsktra.
إذا كانت G مخططًا غير موجّه، فنقول أنّ المخطط S هو مخطط فرعي subgraph من G إذا كانت جميع حروفه وأضلَاعه تنتمي إلى G.
ونقول أنّ S شجرة ممتدة فقط إذا كانت:
- تحتوي جميع عقد G.
- وكانت شجرة، أي أنّها لا تحتوي أيّ دورة cycle، وجميع عقدها متصلة.
- تحتوى (n-1) ضلعًا، حيث n يمثّل عدد العقد في G.
يمكن أن يكون لمخطط ما أكثر من شجرة ممتدة واحدة، والشجرة الممتدة الصغرى لمخطط موزون غير موجّه هي شجرة مجموع أوزان أضلاعها أقل ما يمكن. سنستخدم خوارزمية Prim لإيجاد الشجرة الممتدة الصغرى، وسيساعدنا هذا على حل مشكلة الخطوط الهاتفية في المثال أعلاه.
أولاً، سنختار عقدةً ما لتكون العقدة المصدرية source node، ولتكن العقدة 1 مثلًا. سنضيف الآن الضلع الذي ينطلق من 1 وله أقل كلفة إلى المخطط الفرعي، ونلوّن الأضلاع التي أضفناها إلى المخطط الفرعي باللون الأزرق. وسيكون الضلع 1-5 في مثالنا هو الضلع الذي له أقل كلفة.
الآن، سنأخذ الضلع الأقل كلفة من بين جميع الأضلاع المُنطلِقة من العقدة 1 أو العقدة 5. وبما أنّنا لوّنّا 1-5 سلفًا، فالضلع المرشّح الثاني هو الضلع 1-2.
نأخذ هذه المرة الضلع الأقل كلفةً من بين جميع الأضلاع (غير المُلوّنة) المُنطلقة من العقدة 1 أو العقدة 2 أو العقدة 5، والذي هو في حالتنا 5-4.
تحتاج الخطوة التالية إلى تركيز، وفيها سنحاول أن نفعل ما فعلناه سابقا، ونختار من بين جميع الأضلاع (غير المُلوّنة) التي تنطلق من العقدة 1 أو 2 أو 5 أو 4 الضلع الذي له أقل كلفة، وهو 2-4. ولكن انتبه إلى أنّه في حال اختيار هذا الضلع، فسنخلُق دورةً cycle في المخطط الفرعي، ذلك أنّ العقدتين 2 و4 موجودتان سلفًا فيه، لذا فإنّ أخذ الضلع 2-4 ليس الخيار الصحيح. وبدلًا من ذلك سنختار الضلع 4-8.
إذا واصلنا على هذا النحو فسنختَار الأضلاع 8-6 و6-7 و4-3، وسيبدو المخطط الفرعي النهائي هكذا:
إذا أزلنا الأضلاع التي لم نَخترها (غير المُلوّنة)، فسنحصل على:
هذه هي الشجرة الممتدة الصغرى MST التي نبحث عنها، ونستنتج منها أنّ تكلفة إعداد خطوط الهاتف هي: 4 + 2 + 5 + 11 + 9 + 2 + 1 = 34.
يمكن أن تكون هناك عدة أشجار ممتدة صغرى للمخطط نفسه بحسب العقدة المصدرية التي اخترناها. انظر شيفرة توضيحية لهذه الخوارزمية، حيث تمثل Graph مخططًا فارغًا متصلًا غير موزون، وتمثل Vnew مخططًا فرعيًا جديدًا عقدته المصدرية هي x:
Procedure PrimsMST(Graph): Vnew[] = {x} Enew[] = {} while Vnew is not equal to V u -> a node from Vnew v -> a node that is not in Vnew such that edge u-v has the minimum cost // إذا كان لعقدتين الوزن نفسه، فاختر أيًّا منهما add v to Vnew add edge (u, v) to Enew end while Return Vnew and Enew
التعقيد
التعقيد الزمني للمنظور البسيط أعلاه هو ( O (V 2، يمكننا تقليل التعقيد باستخدام طابور أولويات priority queue، فإذا أضفنا عقدةً جديدةً إلى المخطط الفرعي الجديد Vnew، فيمكننا إضافة أضلاعها المجاورة إلى رتل الأولويات، ثم إخراج الضلع الموزون ذو الكلفة الأدنى منه. وحينئذ يصبح التعقيد مساويًا للقيمة O (ElogE)، حيث يمثّل E عدد الأضلاع. يمكنك أيضًا إنشاء كَومة ثنائية Binary Heap لتخفيض التعقيد إلى O (ElogV).
هذه شيفرة توضيحية تستخدم طابور الأولويات:
Procedure MSTPrim(Graph, source): for each u in V key[u] := inf parent[u] := NULL end for key[source] := 0 Q = Priority_Queue() Q = V while Q is not empty u -> Q.pop for each v adjacent to i if v belongs to Q and Edge(u,v) < key[v] // edge(u, v) كلفة Edge(u, v) تمثل parent[v] := u key[v] := Edge(u, v) end if end for end while
تخزّن key[] الكلفة الأقل لعبور العقدة v، فيما تُستخدم parent[] لتخزين العقدة الأصلية parent node، وهذا مفيد لتسلّق الشجرة وطباعتها. فيما يلي برنامج بسيط بلغة Java:
import java.util.*; public class Graph { private static int infinite = 9999999; int[][] LinkCost; int NNodes; Graph(int[][] mat) { int i, j; NNodes = mat.length; LinkCost = new int[NNodes][NNodes]; for ( i=0; i < NNodes; i++) { for ( j=0; j < NNodes; j++) { LinkCost[i][j] = mat[i][j]; if ( LinkCost[i][j] == 0 ) LinkCost[i][j] = infinite; } } for ( i=0; i < NNodes; i++) { for ( j=0; j < NNodes; j++) if ( LinkCost[i][j] < infinite ) System.out.print( " " + LinkCost[i][j] + " " ); else System.out.print(" * " ); System.out.println(); } } public int unReached(boolean[] r) { boolean done = true; for ( int i = 0; i < r.length; i++ ) if ( r[i] == false ) return i; return -1; } public void Prim( ) { int i, j, k, x, y; boolean[] Reached = new boolean[NNodes]; int[] predNode = new int[NNodes]; Reached[0] = true; for ( k = 1; k < NNodes; k++ ) { Reached[k] = false; } predNode[0] = 0; printReachSet( Reached ); for (k = 1; k < NNodes; k++) { x = y = 0; for ( i = 0; i < NNodes; i++ ) for ( j = 0; j < NNodes; j++ ) { if ( Reached[i] && !Reached[j] && LinkCost[i][j] < LinkCost[x][y] ) { x = i; y = j; } } System.out.println("Min cost edge: (" + + x + "," + + y + ")" + "cost = " + LinkCost[x][y]); predNode[y] = x; Reached[y] = true; printReachSet( Reached ); System.out.println(); } int[] a= predNode; for ( i = 0; i < NNodes; i++ ) System.out.println( a[i] + " --> " + i ); } void printReachSet(boolean[] Reached ) { System.out.print("ReachSet = "); for (int i = 0; i < Reached.length; i++ ) if ( Reached[i] ) System.out.print( i + " "); //System.out.println(); } public static void main(String[] args) { int[][] conn = {{0,3,0,2,0,0,0,0,4}, // 0 {3,0,0,0,0,0,0,4,0}, // 1 {0,0,0,6,0,1,0,2,0}, // 2 {2,0,6,0,1,0,0,0,0}, // 3 {0,0,0,1,0,0,0,0,8}, // 4 {0,0,1,0,0,0,8,0,0}, // 5 {0,0,0,0,0,8,0,0,0}, // 6 {0,4,2,0,0,0,0,0,0}, // 7 {4,0,0,0,8,0,0,0,0} // 8 }; Graph G = new Graph(conn); G.Prim(); } }
صرّف الشيفرة أعلاه باستخدام التعليمة javac Graph.java، وسيكون الخرج الناتج كما يلي:
$ java Graph * 3 * 2 * * * * 4 3 * * * * * * 4 * * * * 6 * 1 * 2 * 2 * 6 * 1 * * * * * * * 1 * * * * 8 * * 1 * * * 8 * * * * * * * 8 * * * * 4 2 * * * * * * 4 * * * 8 * * * * ReachSet = 0 Min cost edge: (0,3)cost = 2 ReachSet = 0 3 Min cost edge: (3,4)cost = 1 ReachSet = 0 3 4 Min cost edge: (0,1)cost = 3 ReachSet = 0 1 3 4 Min cost edge: (0,8)cost = 4 ReachSet = 0 1 3 4 8 Min cost edge: (1,7)cost = 4 ReachSet = 0 1 3 4 7 8 Min cost edge: (7,2)cost = 2 ReachSet = 0 1 2 3 4 7 8 Min cost edge: (2,5)cost = 1 ReachSet = 0 1 2 3 4 5 7 8 Min cost edge: (5,6)cost = 8 ReachSet = 0 1 2 3 4 5 6 7 8 0 --> 0 0 --> 1 7 --> 2 0 --> 3 3 --> 4 2 --> 5 5 --> 6 1 --> 7 0 --> 8
خوارزمية بلمان- فورد Bellman–Ford
خوارزمية بِلمان - فورد Bellman–Ford هي خوارزمية تحاول حساب أقصر المسارات من رأس مصدري source vertex إلى جميع الحروف الأخرى في مخطط موجّه موزون، ورغم أنّ هذه الخوارزمية أبطأ من خوارزمية Dijkstra، إلا أنها تعمل في الحالات التي تكون فيها أوزان الأضلاع سالبة، كما أنّها قادرة على العثور على الدورات ذات الوزن السالب في المخطط، على خلاف خوارزمية Dijkstra التي لا تعمل في حال كانت هناك دورة سالبة، إذ ستستمر في المرور عبر الدورة مرارًا وتكرارًا، وتستمر أيضًا في تقليل المسافة بين الرأسيْن.
تتمثل فكرة هذه الخوارزمية في المرور عبر جميع أضلاع المخطط واحدًا تلو الآخر بترتيب عشوائي، شرط أن يحقق الترتيب المعادلة التالية:
اقتباسلكل u وv، لدينا u < v، فقط إذا كان (هناك ضلع من u إلى v)
بعد تحديد الترتيب، سنخفّف الضلع -تخفيف الضلع هو تخفيض تكلفة الوصول إلى رأس معيّن عبر استخدام رأس آخر وسيط- وفقًا لصيغة التخفيف التالية.
لكل ضلع u-v من u إلى v:
if distance[u] + cost[u][v] < d[v] d[v] = d[u] + cost[u][v]
بمعنى أنّه إذا كانت المسافة من المصدر إلى أيّ رأس u + وزن الضلع u-v < المسافة من المصدر إلى رأس ٍآخر v، فسنحدّث المسافة من المصدر إلى v.
نحتاج إلى تخفيف الأضلاع (V-1) مرّة على الأكثر، حيث V هو عدد الأضلاع في المخطط. سنشرح لاحقًا لماذا اخترنا العدد (V-1)، ونخزّن أيضًا الرأس الأب parent vertex الخاص بكل الرأس، ونكتب ما يلي في كل مرّة نخفّف ضلعًا:
parent[v] = u
هذا يعني أننا وجدنا مسارًا آخر أقصر للوصول إلى v عبر u. سنحتاج أيضًا هذه القيمة المُخزّنة لاحقًا لطباعة أقصر مسار من المصدر إلى الرأس المنشود.
انظر المثال التالي:
لقد اخترنا 1 ليكون الرأس المصدري، والآن نريد العثور على أقصر مسار من هذا المصدر إلى جميع الحروف الأخرى.
نكتب في البداية d[1] = 0، لأنّ 1 هو المصدر؛ أما البقيّة فستساوي اللانهاية لأنّنا لا نعرف مسافاتها بعد. سنخفّف الأضلاع في هذا التسلسل:
+--------+--------+--------+--------+--------+--------+--------+ | التسلسل | 1 | 2 | 3 | 4 | 5 | 6 | +--------+--------+--------+--------+--------+--------+--------+ | الضلع | 4->5 | 3->4 | 1->3 | 1->4 | 4->6 | 2->3 | +--------+--------+--------+--------+--------+--------+--------+
يمكنك أن تختار أيّ تسلسل تريد، إذا خفّفنا الأضلاع مرّةً واحدة، فسنحصل على المسافات من المصدر إلى جميع الرؤوس الأخرى للمسار الذي يستخدم ضلعًا واحدًا على الأكثر.
لنخفّف الآن الأضلاع ونحدث قيم d[]:
- d[4] + cost[4][5] = infinity + 7 = infinity. لا يمكننا تحديث هذا.
- d[2] + cost[3][4] = infinity. لا يمكننا تحديث هذا.
- d[1] + cost[1][3] = 0 + 2 = 2 < d[2] إذًا d[3] = 2 و parent[1] = 1.
- d[1] + cost[1][4] = 4. إذن d[4] = 4 < d[4]. parent[4] = 1.
- d[4] + cost[4][6] = 9. d[6] = 9 < d[6]. parent[6] = 4.
- d[2] + cost[2][3] = infinity لا يمكننا تحديث هذا.
تعذّر تحديث بعض الرؤوس نتيجة عدم تحقّق الشرط d[u] + cost[u][v] < d[v]. وكما قلنا سابقًا، فقد حصلنا على المسارات من المصدر إلى العقد الأخرى باستخدام ضلع واحد على الأكثر.
سيزوّدنا التكرار الثاني بمسار يستخدم عقدتين:
- d[4] + cost[4][5] = 12 < d[5]. d[5] = 12. parent[5] = 4.
- d[3] + cost[3][4] = 1 < d[4]. d[4] = 1. parent[4] = 3
- d[3] تبقى بلا تغيير.
- d[4] تبقى بلا تغيير
- d[4] + cost[4][6] = 6 < d[6]. d[6] = 6. parent[6] = 4.
- d[3] تبقى بلا تغيير.
هكذا سيبدو المخطط:
التكرار الثالث سيحدّث الرأس 5 فقط، حيث سيضع القيمة 8 في d[5]. وسيبدو المخطط هكذا:
بعد هذا، ستبقى المسافة كما هي مهما زِدنا من التكرارات، لذلك سنخزّن راية flag للتحقق من وقوع أيّ تحديث أم لا، فإذا لم يقع أيّ تحديث، أوقفنا حلقة التكرار.
هذه شيفرة توضيحية:
Procedure Bellman-Ford(Graph, source): n := number of vertices in Graph for i from 1 to n d[i] := infinity parent[i] := NULL end for d[source] := 0 for i from 1 to n-1 flag := false for all edges from (u,v) in Graph if d[u] + cost[u][v] < d[v] d[v] := d[u] + cost[u][v] parent[v] := u flag := true end if end for if flag == false break end for Return d
لتتبع الدورات السالبة، سنعدّل الشيفرة كما يلي:
Procedure Bellman-Ford-With-Negative-Cycle-Detection(Graph, source): n := number of vertices in Graph for i from 1 to n d[i] := infinity parent[i] := NULL end for d[source] := 0 for i from 1 to n-1 flag := false for all edges from (u,v) in Graph if d[u] + cost[u][v] < d[v] d[v] := d[u] + cost[u][v] parent[v] := u flag := true end if end for if flag == false break end for for all edges from (u,v) in Graph if d[u] + cost[u][v] < d[v] Return "Negative Cycle Detected" end if end for Return d
لأجل طباعة أقصر مسار إلى رأس معين، سنكّرر خلفيًا إلى الأب parent إلى أن نعثر على القيمة المعدومة NULL، ثمّ نطبع الحروف.
انظر الشيفرة التوضيحية التالية:
Procedure PathPrinting(u) v := parent[u] if v == NULL return PathPrinting(v) print -> u
سيساوي التعقيد الزمني لهذه الخوارزمية O (V * E) إن استخدمنا قائمة تجاور adjacency list بما أننا سنحتاج إلى تخفيف الأضلاع بحد أقصى (V-1) مرة، حيث تشير E إلى عدد الأضلاع؛ أما إن استخدمنا مصفوفة تجاور لتمثيل المخطط، فسيكون التعقيد الزمني O (V ^ 3)، ذلك أننا سنستطيع التكرار على جميع الأضلاع عند استخدام قائمة التجاور خلال زمن قدره O(E)، بينما نستغرق زمنًا قدره O (V ^ 2) إن استخدمنا مصفوفة التجاور.
رصد الدورات السالبة في المخططات
نستطيع رصد أي دورة سالبة في المخطط باستخدام خوارزمية بِلمَن-فورد Bellman-Ford. ونحن نعرف أنه يجب تخفيف جميع أضلاع المخطط عدد (V-1) مرة من أجل العثور على أقصر مسار، حيث تمثل V عدد الرؤوس في المخطط، وقد رأينا أنه لا يمكن تحديث d[] مهما كان عدد التكرارات التي أجريناها.
إذا كانت هناك دورة سالبة في المخطط، فسيمكننا تحديث d[] حتى بعد التكرار (V-1)، ذلك أن كل تكرار، سيقلل العبور خلال دورة سالبة تكلفةَ المسار الأقصر، وهذا سبب أن خوارزمية بِلمَن فورد تحد عدد التكرارات بـ (V-1) مرة، لأننا سنعلق داخل حلقة أبدية لا تنتهي إن استخدمنا خوارزمية ديكسترا. سنركز الآن على كيفية إيجاد دورة سالبة، انظر المخطط التالي:
لنختر الرأس1 ليكون المصدر، بعد تطبيق خوارزمية بلمان-فورد لأقصر مسار ذي مصدر وحيد على المخطط، سنجد المسافات التي تفصل المصدر عن جميع الرؤوس الأخرى. انظر:
هكذا سيبدو المخطط بعد (V-1) = 3 تكرار، وينبغي أن تكون هذه هي النتيجة الصحيحة، لأنّنا سنحتاج 3 تكرارات على الأكثر للعثور على أقصر مسار ما دامت هناك 4 أضلاع في المخطط، لذا إمّا أنّ هذه هي الإجابة الصحيحة، وإمّا أنّ هناك دورة ذات وزن سالب في المخطط. ولنعرف ذلك، سنضيف تكرارًا جديدًا بعد التكرار (V-1)، فإذا استمرت المسافة في الانخفاض، فذلك يعني أنّ هناك دورة سالبة في المخطط.
ولهذا المثال فإنه بالنسبة للضلع 2-3، تكون نتيجة d[2] + cost [2] [3] مساوية لـ 1، وهو أقل من d[3]، لذا يمكننا أن نستنتج أنّ هناك دورةً سالبةً في المخطط. والسؤال الآن هو كيف نجد هذه الدورة السالبة؟
سنجري تعديلًا بسيطًا على خوارزمية Bellman-Ford للعثور على الدورة السالبة:
Procedure NegativeCycleDetector(Graph, source): n := number of vertices in Graph for i from 1 to n d[i] := infinity end for d[source] := 0 for i from 1 to n-1 flag := false for all edges from (u,v) in Graph if d[u] + cost[u][v] < d[v] d[v] := d[u] + cost[u][v] flag := true end if end for if flag == false break end for for all edges from (u,v) in Graph if d[u] + cost[u][v] < d[v] Return "Negative Cycle Detected" end if end for Return "No Negative Cycle"
بهذه الطريقة نستطيع التحقق مما إذا كانت هناك أيّ دورة سالبة في المخطط، كذلك نستطيع تعديل خوارزمية Bellman-Ford لتخزين الدورات السالبة وحفظ سجل لها.
لماذا نحتاج إلى تخفيف جميع الأضلاع بحد أقصى (V-1) مرة
نحتاج إلى تخفيف جميع أضلاع المخطط في خوارزمية Bellman-Ford للعثور على أقصر مسار، وتُكرّر هذه العملية (V-1) مرّةً بحد أقصى، حيث يمثل V عدد الرؤوس في المخطط. ويعتمد عدد التكرارات اللازمة للعثور على أقصر مسار من المصدر إلى جميع الرؤوس الأخرى على الترتيب الذي اخترناه لتخفيف الأضلاع. انظر المثال التالي:
لقد اخترنا الرأس 1 ليكون المصدر، سنبحث عن أقصر مسافة تفصل بين المصدر وجميع الحروف الأخرى. ونستطيع رؤية أننا سنحتاج في أسوأ الأحوال إلى (V-1) ضلع للوصول إلى الرأس 4، ووفقًا للترتيب الذي اكتُشفت من خلاله الأضلاع، فقد نحتاج إلى (V-1) مرة.
للتوضيح، سنستخدم خوارزمية Bellman-Ford في مثال توضيحي للعثور على أقصر مسار.
انظر التسلسل التالي:
+--------+--------+--------+------+ | التسلسل | 1 | 2 | 3 | +--------+--------+--------+------+ | الضلع | 3->4 | 2->3 | 1->2 | +--------+--------+--------+------+
في التكرار الأول:
- d[3] + cost[3][4] = infinity لن يحدث أيّ تغيير.
- d[2] + cost[2][3] = infinity لن يحدث أيّ تغيير.
- d[1] + cost[1][2] = 2 < d[2]. d[2] = 2. parent[2] = 1.
لاحظ أنّ عملية التخفيف لم تغيّر إلا قيمة d[2] فقط. سيبدو المخطط خاصتنا هكذا:
التكرار الثاني:
- d[3] + cost[3][4] = infinity لن يحدث أيّ تغيير.
- d[2] + cost[2][3] = 5 < d[3]. d[3] = 5. parent[3] = 2.
- لن يحدث أيّ تغيير.
غيّرت عمليةُ التخفيف قيمةَ d[3] في هذه المرّة. وسيبدو المخطط هكذا:
التكرار الثالث:
- d[3] + cost[3][4] = 7 < d[4] . d[4] = 7 . parent[4] = 3 .
- لن يحدث أيّ تغيير.
- لن يحدث أيّ تغيير.
وجدنا في التكرار الثالث أقصر مسار إلى 4 من المصدر 1، حيث سيبدو المخطط هكذا:
احتجنا إلى 3 تكرارات للعثور على أقصر مسار. ستظل قيمة d[] كما هي بعد ذلك مهما حاولنا تخفيف الأضلاع. إليك تسلسلًا آخر:
+--------+--------+--------+------+ | التسلسل | 1 | 2 | 3 | +--------+--------+--------+------+ | الضلع | 1->2 | 2->3 | 3->4 | +--------+--------+--------+------+
سنحصل على:
- d[1] + cost[1][2] = 2 < d[2] . d[2] = 2 .
- d[2] + cost[2][3] = 5 < d[3]. d[3] = 5.
- d[3] + cost[3][4] = 7 < d[4]. d[4] = 5.
وجدنا أقصر مسار من المصدر إلى جميع العقد الأخرى منذ التكرار الأول، يمكننا إجراء التسلسلات الإضافية 1-> 2 و3-> 4 و 2-> 3، والتي ستعطينا أقصر مسار بعد تكرارين. يقودنا هذا إلى استنتاج أنه مهما كان ترتيب التسلسل، فلن نحتاج أكثر من 3 تكرارات للعثور على أقصر مسار من المصدر.
نستنتج أيضًا أننا قد لا نحتاج في بعض الحالات إلّا إلى تكرار واحد فقط للعثور على أقصر مسار من المصدر. وسنحتاج في أسوأ الحالات إلى (V-1) تكرار. أرجو أن تكون قد فهمت الآن لماذا ينبغي أن نكرّر عملية التخفيف (V-1) مرّة.
خوارزمية فلويد وورشال Floyd-Warshall
تُستخدم خوارزمية فلويد وورشال Floyd-Warsha ll لإيجاد أقصر المسارات في مخطط موزون قد تكون أوزان أضلاعه موجبة أو سالبة.
عند تنفيذ الخوارزمية مرّةً واحدة، سنحصل على أطوال -مجاميع أوزان- أقصر المسارات بين كل أزواج الرؤوس، ويمكنها -بقليل من التعديل- طباعة أقصر مسار، كما يمكنها رصد الدورات السالبة في المخطط. وخوارزمية Floyd- Warshall هي من خوارزميات البرمجة الديناميكية. لنطبق هذه الخوارزمية على المخطط التالي:
أول شيء نفعله هو أخذ مصفوفتين ثنائيتَي الأبعاد لتكونا مصفُوفتي تجاور adjacency matrices يساوي حجماهما العدد الإجمالي للرؤوس. وفي مثالنا، سنأخذ مصفوفتين من الحجم 4*4، الأولى هي مصفوفة المسافات Distance Matrix، وسنخزّن فيها أقصر مسافة عثرنا عليها حتى الآن بين رأسين.
بدايةً، إذا كان هناك ضلع بين u-v وكانت المسافة / الوزن = w، فإننا نضع distance[u][v] = w، وسنضع قيمة ما لا نهاية للأضلاغ غير الموجودة.
المصفوفة الثانية هي مصفوفة المسارات Path Matrix، ونستخدمها لتوليد أقصر مسار بين رأسين، لذا إذا كان هناك مسار بين u وv، فسنضع path[u][v] = u، وهذا يعني أنّ أفضل طريقة للوصول إلى الرأس v انطلاقًا من u هو باستخدام الضلع الذي يربط v بـ u، وإذا لم يكن هناك مسار بين الرأسين، فسنعطيه القيمة N كناية على عدم وجود مسار متاح حاليًا. سيبدو جدولا المخطط كما يلي:
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+ | | 1 | 2 | 3 | 4 | | | 1 | 2 | 3 | 4 | +-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+ | 1 | 0 | 3 | 6 | 15 | | 1 | N | 1 | 1 | 1 | +-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+ | 2 | inf | 0 | -2 | inf | | 2 | N | N | 2 | N | +-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+ | 3 | inf | inf | 0 | 2 | | 3 | N | N | N | 3 | +-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+ | 4 | 1 | inf | inf | 0 | | 4 | 4 | N | N | N | +-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+ المسار المسافة
وقد وضعنا الرأس N في المواضع القطرية diagonals في مصفوفة المسارات نظرًا لعدم وجود حلقة loop، ولما كانت المسافة من كل رأس إلى نفسه تساوي 0، فقد وضعنا القيمة 0 في المواضع القطرية في مصفوفة المسافات.
سنختار رأسًا وسطيًا k لأجل تطبيق خوارزمية Floyd-Warshall، وسنتحق بعد ذلك لكلّ رأس i مما إن كنا نستطيع الانتقال من i إلى k ثم من k إلى j، حيث j يمثّل رأسًا آخر، لتقليل تكلفة الانتقال من i إلى j.
إذا كانت المسافة distance [j] أكبر من المسافة distance [k] + distance[k] [j]، فسنحدّث قيمة distance [j]، ونضع فيها مجموع هاتين المسافتين، كما سنحدّث path [j] ونعطيها القيمة path[k] [j]، لأنّ الانتقال من i إلى k، ثم من k إلى j أفضل. كما ستٌختار جميع الرؤوس بنفس طريقة اختيار k. وهكذا نحصل على 3 حلقات متداخلة:
-
k من 1 إلى 4.
-
i من 1 إلى 4.
- j من 1 إلى 4.
-
i من 1 إلى 4.
هذه شيفرة توضيحية لذلك:
if distance[i][j] > distance[i][k] + distance[k][j] distance[i][j] := distance[i][k] + distance[k][j] path[i][j] := path[k][j] end if
السؤال الآن هو: لكل زوج u,v من الرؤوس، هل يوجد رأس يمكن أن نمرّ عبره لتقصير المسافة بين u وv؟
سيكون العدد الإجمالي لعمليات المخطط هو 4 * 4 * 4 = 64. وهذا يعني أنّنا سنجري هذا الاختبار 64 مرة، لنلقي نظرةً على بعض هذه الحالات:
- إذا كانت k = 1 وi = 2 وj = 3، فإن [distance [j ستساوي -2، وهي ليست أكبر من distance [k] + distance[k] [j] = -2 + 0 = -2، لذلك ستبقى دون تغيير.
- ومرةً أخرى، إذا كانت k = 1 وi = 4 وj = 2، فستكون distance [j] = infinity، وهي أكبر من distance [k] + distance[k] [j] = 1 + 3 = 4، لذا نضع distance [j] = 4، وpath [j] = path[k] [j] = 1. وهذا يعني أنّه للانتقال من الرأس 4 إلى 2، فإنّ المسار 4-> 1-> 2 يكون أقصر من المسار الحالي.
انظر هذا الرابط الأجنبي للاطلاع على حسابات كل خطوة، وستبدو مصفوفتنا كما يلي بعد إجراء التعديلات اللازمة.
بعد إجراء التغييرات اللازمة، ستبدو المصفوفتان كما يلي:
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+ | | 1 | 2 | 3 | 4 | | | 1 | 2 | 3 | 4 | +-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+ | 1 | 0 | 3 | 1 | 3 | | 1 | N | 1 | 2 | 3 | +-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+ | 2 | 1 | 0 | -2 | 0 | | 2 | 4 | N | 2 | 3 | +-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+ | 3 | 3 | 6 | 0 | 2 | | 3 | 4 | 1 | N | 3 | +-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+ | 4 | 1 | 4 | 2 | 0 | | 4 | 4 | 1 | 2 | N | +-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+ المسار المسافة
وهكذا نكون قد حصلنا على مصفوفةِ أقصر المسافات، فمثلًا، تكون أقصر مسافة من 1 إلى 4 هي 3، وأقصر مسافة من 4 إلى 3 هي 2. انظر إلى الشيفرة التوضيحية التالية، حيث تمثل V عدد الرؤوس:
Procedure Floyd-Warshall(Graph): for k from 1 to V for i from 1 to V for j from 1 to V if distance[i][j] > distance[i][k] + distance[k][j] distance[i][j] := distance[i][k] + distance[k][j] path[i][j] := path[k][j] end if end for end for end for
سنتحقق من مصفوفة المسارات Path من أجل طباعة المسار، ولطباعة المسار من u إلى v، سنبدأ من path[u] [v]. ثمّ نستمر في تغيير v = path[u] [v] إلى أن نحصل على path[u] [v] = u، وندفع كل قيم path[u] [v] إلى مكدّس.
بعد العثور على الرأس u، سنطبع u ونبدأ بإخراج العناصر من المكدّس وطباعتها. هذا الأمر ممكن لأنّ مصفوفة المسارات تخزّن قيمة الرأس الذي يشارك في أقصر مسار إلى v انطلاقًا من أيّ عقدة أخرى.
انظر إلى الشيفرة التوضيحية لذلك:
Procedure PrintPath(source, destination): s = Stack() S.push(destination) while Path[source][destination] is not equal to source S.push(Path[source][destination]) destination := Path[source][destination] end while print -> source while S is not empty print -> S.pop end while
من أجل التحقق من وجود دورة سالبة، سيكون علينا التحقق من القطر diagonal الرئيسي لمصفوفة المسافات، وإذا كانت أيٌّ من القيم القطرية diagonal سالبة، فهذا يعني وجود دورة سالبة في المخطط.
إن تعقيد خوارزمية فلويد-وورشال Floyd-Warshall هو O (V3)، وتعقيد المساحة هو: O (V2).
ترجمة -بتصرّف- للفصول 19 و20 و22 من كتاب Algorithms Notes for Professionals.
أفضل التعليقات
لا توجد أية تعليقات بعد
انضم إلى النقاش
يمكنك أن تنشر الآن وتسجل لاحقًا. إذا كان لديك حساب، فسجل الدخول الآن لتنشر باسم حسابك.