سيعلمنا البرنامج التعليمي التالي عن خوارزمية Dijkstra لأقصر مسار. سوف نفهم عمل خوارزمية ديكسترا من خلال شرح رسومي متدرج.

سنغطي ما يلي:

• لمحة موجزة عن المفاهيم الأساسية للرسم البياني
• فهم استخدام خوارزمية ديكسترا
• افهم طريقة عمل الخوارزمية من خلال مثال خطوة بخطوة

اذا هيا بنا نبدأ.

مقدمة موجزة للرسوم البيانية

الرسوم البيانية هي هياكل بيانات غير خطية تمثل 'الاتصالات' بين العناصر. تُعرف هذه العناصر باسم الرؤوس وتعرف الخطوط أو الأقواس التي تربط أي رأسين في الرسم البياني باسم حواف . وبشكل أكثر رسمية، يتضمن الرسم البياني مجموعة من القمم (V) و مجموعة من الحواف (E) . يشار إلى الرسم البياني بواسطة ز(الخامس، ه) .

مكونات الرسم البياني

الرؤوس:القمم هي الوحدات الأساسية للرسم البياني المستخدم لتمثيل الأشياء أو الأشخاص أو الكيانات الواقعية. في بعض الأحيان، تُعرف القمم أيضًا باسم العقد.حواف:يتم رسم الحواف أو استخدامها لربط رأسين من الرسم البياني. في بعض الأحيان، تُعرف الحواف أيضًا باسم الأقواس.

يوضح الشكل التالي تمثيلاً رسوميًا للرسم البياني:

شكل 1: التمثيل الرسومي للرسم البياني

في الشكل أعلاه، تتم الإشارة إلى القمم/العقد بدوائر ملونة، ويتم الإشارة إلى الحواف بالخطوط التي تربط العقد.

تطبيقات الرسوم البيانية

تُستخدم الرسوم البيانية لحل العديد من مشكلات الحياة الواقعية. يتم استخدام الرسوم البيانية لتمثيل الشبكات. قد تشمل هذه الشبكات شبكات الهاتف أو الدوائر أو المسارات في المدينة.

على سبيل المثال، يمكننا استخدام الرسوم البيانية لتصميم نموذج شبكة النقل حيث تعرض القمم المرافق التي ترسل أو تستقبل المنتجات، وتمثل الحواف الطرق أو المسارات التي تربط بينها. وفيما يلي تمثيل تصويري للنفس:

الشكل 2: التمثيل التصويري لشبكة النقل

تُستخدم الرسوم البيانية أيضًا في منصات التواصل الاجتماعي المختلفة مثل LinkedIn وFacebook وTwitter والمزيد. على سبيل المثال، تستخدم منصات مثل Facebook الرسوم البيانية لتخزين بيانات مستخدميها حيث تتم الإشارة إلى كل شخص بنقطة قمة، وكل واحد منهم عبارة عن بنية تحتوي على معلومات مثل معرف الشخص والاسم والجنس والعنوان وما إلى ذلك.

أنواع الرسوم البيانية

يمكن تصنيف الرسوم البيانية إلى نوعين:

1. الرسم البياني غير الموجه
2. مخطط موجه

الرسم البياني غير الموجه: يسمى الرسم البياني ذو الحواف التي ليس لها اتجاه بالرسم البياني غير الموجه. تشير حواف هذا الرسم البياني إلى وجود علاقة ذات اتجاهين حيث يمكن اجتياز كل حافة في كلا الاتجاهين. يعرض الشكل التالي رسمًا بيانيًا بسيطًا غير موجه بأربع عقد وخمس حواف.

الشكل 3: رسم بياني بسيط غير موجه

مخطط موجه: يسمى الرسم البياني ذو الحواف ذات الاتجاه بالرسم البياني الموجه. تشير حواف هذا الرسم البياني إلى علاقة أحادية الاتجاه حيث لا يمكن اجتياز كل حافة إلا في اتجاه واحد. يعرض الشكل التالي رسمًا بيانيًا موجهًا بسيطًا يحتوي على أربع عقد وخمس حواف.

الشكل 4: رسم بياني موجه بسيط

الطول المطلق أو الموضع أو الاتجاه للحواف في الرسم التوضيحي ليس له معنى بشكل مميز. بمعنى آخر، يمكننا تصور نفس الرسم البياني بطرق مختلفة عن طريق إعادة ترتيب القمم أو تشويه الحواف إذا لم يتغير الهيكل الأساسي للرسم البياني.

ما هي الرسوم البيانية المرجحة؟

يقال إن الرسم البياني مرجح إذا تم تعيين 'وزن' لكل حافة. يمكن أن يشير وزن الحافة إلى المسافة أو الوقت أو أي شيء يمثل 'الاتصال' بين زوج القمم التي تتصل بها.

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

الشكل 5: مثال على الرسم البياني المرجح

مقدمة لخوارزمية ديكسترا

الآن بعد أن عرفنا بعض المفاهيم الأساسية للرسومات البيانية، دعونا نتعمق في فهم مفهوم خوارزمية ديكسترا.

هل تساءلت يومًا كيف تعثر خرائط Google على أقصر وأسرع طريق بين مكانين؟

حسنا، الجواب هو خوارزمية ديكسترا . خوارزمية ديكسترا هي خوارزمية الرسم البياني الذي يجد أقصر طريق من قمة المصدر إلى جميع القمم الأخرى في الرسم البياني (مصدر واحد أقصر مسار). إنه نوع من الخوارزميات الجشعة التي تعمل فقط على الرسوم البيانية الموزونة ذات الأوزان الإيجابية. التعقيد الزمني لخوارزمية ديكسترا هو يا(ف²) بمساعدة تمثيل مصفوفة المجاورة للرسم البياني. يمكن تقليل التعقيد هذا الوقت إلى O((V + E) سجل V) مع مساعدة من تمثيل قائمة المجاورة للرسم البياني، حيث في هو عدد القمم و و هو عدد الحواف في الرسم البياني.

تاريخ خوارزمية ديكسترا

تم تصميم ونشر خوارزمية ديكسترا بواسطة دكتور. إدسجر دبليو ديكسترا ، عالم كمبيوتر هولندي، ومهندس برمجيات، ومبرمج، وكاتب مقالات علمية، وعالم أنظمة.

خلال مقابلة مع فيليب ل. فرانا للاتصالات في مجلة ACM في عام 2001، كشف الدكتور إدسجر دبليو ديكسترا:

'ما هو أقصر طريق للسفر من روتردام إلى جرونينجن بشكل عام: من مدينة معينة إلى مدينة معينة؟' إنها خوارزمية أقصر مسار، والتي صممتها في حوالي عشرين دقيقة. في صباح أحد الأيام كنت أتسوق في أمستردام مع خطيبتي الصغيرة، وكنت متعبًا، جلسنا على شرفة المقهى لنحتسي فنجانًا من القهوة وكنت أفكر فقط فيما إذا كان بإمكاني القيام بذلك، ثم صممت الخوارزمية لأقصر طريق . كما قلت، كان اختراعًا مدته عشرين دقيقة. في الواقع، تم نشره في عام 1959، بعد ثلاث سنوات. لا يزال المنشور قابلاً للقراءة، وهو في الواقع لطيف جدًا. أحد أسباب جمالها هو أنني صممتها بدون قلم رصاص وورقة. تعلمت لاحقًا أن إحدى مزايا التصميم بدون قلم رصاص وورقة هو أنك مجبر تقريبًا على تجنب كل التعقيدات التي يمكن تجنبها. في نهاية المطاف، أصبحت هذه الخوارزمية مصدر دهشة كبيرة لي، وأحد الركائز الأساسية لشهرتي.

فكر ديكسترا في مسألة أقصر مسار أثناء عمله كمبرمج في مركز الرياضيات في أمستردام عام 1956 لتوضيح قدرات جهاز كمبيوتر جديد يُعرف باسم ARMAC. كان هدفه هو اختيار المشكلة والحل (الذي ينتجه الكمبيوتر) بحيث يمكن للأشخاص الذين ليس لديهم خلفية كمبيوترية فهمه. قام بتطوير خوارزمية المسار الأقصر ثم نفذها لاحقًا لشركة ARMAC للحصول على خريطة نقل مختصرة بشكل غامض لـ 64 مدينة في هولندا (64 مدينة، لذا فإن 6 بتات ستكون كافية لتشفير رقم المدينة). وبعد مرور عام، واجه مشكلة أخرى من مهندسي الأجهزة الذين يقومون بتشغيل الكمبيوتر التالي للمعهد: تقليل كمية الأسلاك المطلوبة لتوصيل المسامير الموجودة على اللوحة الخلفية للجهاز. كحل، أعاد اكتشاف الخوارزمية التي تسمى خوارزمية الشجرة الممتدة الأصغر لبريم ونشرها في عام 1959.

أساسيات خوارزمية ديكسترا

فيما يلي المفاهيم الأساسية لخوارزمية Dijkstra:

1. تبدأ خوارزمية ديكسترا من العقدة التي نختارها (العقدة المصدر)، وتقوم بفحص الرسم البياني للعثور على أقصر مسار بين تلك العقدة وجميع العقد الأخرى في الرسم البياني.
2. تحتفظ الخوارزمية بسجلات لأقصر مسافة معترف بها حاليًا من كل عقدة إلى العقدة المصدر، وتقوم بتحديث هذه القيم إذا وجدت أي مسار أقصر.
3. بمجرد قيام الخوارزمية باسترداد أقصر مسار بين المصدر وعقدة أخرى، يتم وضع علامة على تلك العقدة على أنها 'تمت الزيارة' ويتم تضمينها في المسار.
4. يستمر الإجراء حتى يتم تضمين جميع العقد الموجودة في الرسم البياني في المسار. بهذه الطريقة، يكون لدينا مسار يربط العقدة المصدر بجميع العقد الأخرى، متبعًا أقصر مسار ممكن للوصول إلى كل عقدة.

فهم عمل خوارزمية ديكسترا

أ رسم بياني و قمة المصدر هي متطلبات خوارزمية Dijkstra. تم إنشاء هذه الخوارزمية على نهج الجشع وبالتالي تجد الخيار الأمثل محليًا (الحد الأدنى المحلي في هذه الحالة) في كل خطوة من خطوات الخوارزمية.

سيكون لكل قمة في هذه الخوارزمية خاصيتين محددتين لها:

1. الممتلكات التي تمت زيارتها
2. خاصية المسار

دعونا نفهم هذه الخصائص باختصار.

الممتلكات التي تمت زيارتها:

1. تشير خاصية 'الزيارة' إلى ما إذا كانت العقدة قد تمت زيارتها أم لا.
2. نحن نستخدم هذه الخاصية حتى لا نعيد زيارة أي عقدة.
3. يتم وضع علامة على العقدة بأنها تمت زيارتها فقط عند العثور على أقصر مسار.

خاصية المسار:

1. تقوم خاصية 'المسار' بتخزين قيمة الحد الأدنى الحالي للمسار إلى العقدة.
2. يشير المسار الأدنى الحالي إلى أقصر طريق وصلنا إلى هذه العقدة حتى الآن.
3. تتم مراجعة هذه الخاصية عند زيارة أي جار للعقدة.
4. هذه الخاصية مهمة لأنها ستخزن الإجابة النهائية لكل عقدة.

في البداية، نضع علامة على جميع القمم، أو العقد، التي لم تتم زيارتها، حيث لم تتم زيارتها بعد. يتم أيضًا تعيين المسار إلى جميع العقد إلى ما لا نهاية بصرف النظر عن العقدة المصدر. علاوة على ذلك، يتم تعيين المسار إلى العقدة المصدر على الصفر (0).

نقوم بعد ذلك بتحديد العقدة المصدر ووضع علامة عليها على أنها تمت زيارتها. بعد ذلك، نصل إلى جميع العقد المجاورة للعقدة المصدر ونجري الاسترخاء على كل عقدة. الاسترخاء هو عملية خفض تكلفة الوصول إلى العقدة بمساعدة عقدة أخرى.

في عملية الاسترخاء، تتم مراجعة مسار كل عقدة إلى الحد الأدنى من القيمة بين المسار الحالي للعقدة، ومجموع المسار إلى العقدة السابقة، والمسار من العقدة السابقة إلى العقدة الحالية.

لنفترض أن p[n] هي قيمة المسار الحالي للعقدة n، وp[m] هي قيمة المسار حتى العقدة التي تمت زيارتها مسبقًا m، وw هو وزن الحافة بين العقدة الحالية و تمت زيارته مسبقًا (وزن الحافة بين n وm).

بالمعنى الرياضي، يمكن تمثيل الاسترخاء على النحو التالي:

ع[ن] = الحد الأدنى(ص[ن]، ص[م] + ث)

نقوم بعد ذلك بوضع علامة على العقدة غير التي تمت زيارتها بأقل مسار تمت زيارتها في كل خطوة لاحقة ونقوم بتحديث مسارات جارتها.

نكرر هذا الإجراء حتى يتم وضع علامة على جميع العقد في الرسم البياني التي تمت زيارتها.

عندما نضيف عقدة إلى المجموعة التي تمت زيارتها، فإن المسار إلى جميع العقد المجاورة لها يتغير أيضًا وفقًا لذلك.

إذا تُركت أي عقدة غير قابلة للوصول (مكون غير متصل)، فسيظل مسارها 'لا نهاية'. في حالة كون المصدر نفسه مكونًا منفصلاً، فإن المسار إلى جميع العقد الأخرى يظل 'لا نهاية'.

فهم خوارزمية ديكسترا مع مثال

فيما يلي الخطوة التي سنتبعها لتنفيذ خوارزمية Dijkstra:

الخطوة 1: أولاً، سنضع علامة على العقدة المصدر بمسافة حالية تبلغ 0 ونضبط بقية العقد على INFINITY.

الخطوة 2: سنقوم بعد ذلك بتعيين العقدة غير التي تمت زيارتها بأصغر مسافة حالية كالعقدة الحالية، لنفترض X.

الخطوه 3: لكل جار N للعقدة الحالية X: سنضيف بعد ذلك المسافة الحالية لـ X مع وزن الحافة التي تربط X-N. إذا كانت أصغر من المسافة الحالية N، فاضبطها على أنها المسافة الحالية الجديدة N.

الخطوة 4: سنقوم بعد ذلك بوضع علامة على العقدة الحالية X على أنها تمت زيارتها.

الخطوة 5: سوف نكرر العملية من 'الخطوة 2' إذا كان هناك أي عقدة لم تتم زيارتها في الرسم البياني.

دعونا الآن نفهم تنفيذ الخوارزمية بمساعدة مثال:

الشكل 6: الرسم البياني المعطى

1. سوف نستخدم الرسم البياني أعلاه كمدخل، مع العقدة أ كمصدر.
2. أولاً، سنضع علامة على جميع العقد على أنها غير تمت زيارتها.
3. سنحدد الطريق إليه 0 في العقدة أ و ما لا نهاية لجميع العقد الأخرى.
4. سنقوم الآن بوضع علامة على العقدة المصدر أ كما تمت زيارتها والوصول إلى العقد المجاورة لها.
   ملحوظة: لقد وصلنا فقط إلى العقد المجاورة، ولم نقم بزيارتها.
5. سنقوم الآن بتحديث المسار إلى العقدة ب بواسطة 4 بمساعدة الاسترخاء لأن المسار إلى العقدة أ يكون 0 والمسار من العقدة أ ل ب يكون 4 ، و ال الحد الأدنى ((0 + 4)، ما لا نهاية) يكون 4 .
6. سنقوم أيضًا بتحديث المسار إلى العقدة ج بواسطة 5 بمساعدة الاسترخاء لأن المسار إلى العقدة أ يكون 0 والمسار من العقدة أ ل ج يكون 5 ، و ال الحد الأدنى ((0 + 5)، ما لا نهاية) يكون 5 . كل من جيران العقدة أ الآن استرخوا؛ ولذلك، يمكننا المضي قدما.
7. سنختار الآن العقدة التالية التي لم تتم زيارتها ذات المسار الأقل ونقوم بزيارتها. وبالتالي، سوف نقوم بزيارة العقدة ب وأداء الاسترخاء على جيرانها غير المأهولة. بعد إجراء الاسترخاء، المسار إلى العقدة ج سيبقى 5 ، في حين أن المسار إلى العقدة و سيصبح أحد عشر ، والمسار إلى العقدة د سيصبح 13 .
8. سنقوم الآن بزيارة العقدة و وإجراء الاسترخاء على العقد المجاورة لها ب، د ، و F . منذ العقدة الوحيدة F لم تتم زيارتها، وسوف يكون مريحا. وبالتالي فإن الطريق إلى العقدة ب سيبقى كما هو، أي 4 ، المسار إلى العقدة د سوف تبقى أيضا 13 ، والمسار إلى العقدة F سيصبح 14 (8 + 6) .
9. الآن سنقوم بزيارة العقدة د ، والعقدة فقط F سوف تكون مريحة. ومع ذلك، فإن المسار إلى العقدة F سوف تبقى دون تغيير، أي، 14 .
10. منذ العقدة الوحيدة F المتبقية، سنقوم بزيارتها ولكن لن نقوم بأي استرخاء حيث تمت زيارة جميع العقد المجاورة لها بالفعل.
11. بمجرد زيارة كافة العقد من الرسوم البيانية، سينتهي البرنامج.

ومن ثم فإن المسارات النهائية التي توصلنا إليها هي:

 A = 0 B = 4 (A -> B) C = 5 (A -> C) D = 4 + 9 = 13 (A -> B -> D) E = 5 + 3 = 8 (A -> C -> E) F = 5 + 3 + 6 = 14 (A -> C -> E -> F) 

الكود الزائف لخوارزمية ديكسترا

سوف نفهم الآن الكود الكاذب لخوارزمية ديكسترا.

• علينا أن نحتفظ بسجل لمسافة المسار لكل عقدة. لذلك، يمكننا تخزين مسافة المسار لكل عقدة في مصفوفة بالحجم n، حيث n هو العدد الإجمالي للعقد.
• علاوة على ذلك، نريد استرداد أقصر مسار مع طول هذا المسار. للتغلب على هذه المشكلة، سنقوم بتعيين كل عقدة إلى العقدة التي قامت بتحديث طول مسارها آخر مرة.
• بمجرد اكتمال الخوارزمية، يمكننا إرجاع العقدة الوجهة إلى العقدة المصدر لاسترداد المسار.
• يمكننا استخدام الحد الأدنى من قائمة انتظار الأولوية لاسترداد العقدة ذات مسافة المسار الأقل بطريقة فعالة.

دعونا الآن ننفذ كودًا زائفًا للرسم التوضيحي أعلاه:

كود مزيف:

 function Dijkstra_Algorithm(Graph, source_node) // iterating through the nodes in Graph and set their distances to INFINITY for each node N in Graph: distance[N] = INFINITY previous[N] = NULL If N != source_node, add N to Priority Queue G // setting the distance of the source node of the Graph to 0 distance[source_node] = 0 // iterating until the Priority Queue G is not empty while G is NOT empty: // selecting a node Q having the least distance and marking it as visited Q = node in G with the least distance[] mark Q visited // iterating through the unvisited neighboring nodes of the node Q and performing relaxation accordingly for each unvisited neighbor node N of Q: temporary_distance = distance[Q] + distance_between(Q, N) // if the temporary distance is less than the given distance of the path to the Node, updating the resultant distance with the minimum value if temporary_distance <distance[n] distance[n] :="temporary_distance" previous[n] returning the final list of distance return distance[], previous[] < pre> <p> <strong>Explanation:</strong> </p> <p>In the above pseudocode, we have defined a function that accepts multiple parameters - the Graph consisting of the nodes and the source node. Inside this function, we have iterated through each node in the Graph, set their initial distance to <strong>INFINITY</strong> , and set the previous node value to <strong>NULL</strong> . We have also checked whether any selected node is not a source node and added the same into the Priority Queue. Moreover, we have set the distance of the source node to <strong>0</strong> . We then iterated through the nodes in the priority queue, selected the node with the least distance, and marked it as visited. We then iterated through the unvisited neighboring nodes of the selected node and performed relaxation accordingly. At last, we have compared both the distances (original and temporary distance) between the source node and the destination node, updated the resultant distance with the minimum value and previous node information, and returned the final list of distances with their previous node information.</p> <h2>Implementation of Dijkstra&apos;s Algorithm in Different Programming Languages</h2> <p>Now that we have successfully understood the pseudocode of Dijkstra&apos;s Algorithm, it is time to see its implementation in different programming languages like C, C++, Java, and Python.</p> <h3>Code for Dijkstra&apos;s Algorithm in C</h3> <p>The following is the implementation of Dijkstra&apos;s Algorithm in the C Programming Language:</p> <p> <strong>File: DijkstraAlgorithm.c</strong> </p> <pre> // Implementation of Dijkstra&apos;s Algorithm in C // importing the standard I/O header file #include // defining some constants #define INF 9999 #define MAX 10 // prototyping of the function void DijkstraAlgorithm(int Graph[MAX][MAX], int size, int start); // defining the function for Dijkstra&apos;s Algorithm void DijkstraAlgorithm(int Graph[MAX][MAX], int size, int start) { int cost[MAX][MAX], distance[MAX], previous[MAX]; int visited_nodes[MAX], counter, minimum_distance, next_node, i, j; // creating cost matrix for (i = 0; i <size; i++) for (j="0;" j < size; j++) if (graph[i][j]="=" 0) cost[i][j]="INF;" else (i="0;" i { distance[i]="cost[start][i];" previous[i]="start;" visited_nodes[i]="0;" } distance[start]="0;" visited_nodes[start]="1;" counter="1;" while (counter size - 1) minimum_distance="INF;" (distance[i] && !visited_nodes[i]) next_node="i;" visited_nodes[next_node]="1;" (!visited_nodes[i]) (minimum_distance + cost[next_node][i] distance[i]) cost[next_node][i]; counter++; printing the distance !="start)" printf('
distance from source node to %d: %d', i, distance[i]); main function int main() defining variables graph[max][max], j, size, source; declaring of matrix nodes graph graph[0][0]="0;" graph[0][1]="4;" graph[0][2]="0;" graph[0][3]="0;" graph[0][4]="0;" graph[0][5]="8;" graph[0][6]="0;" graph[1][0]="4;" graph[1][1]="0;" graph[1][2]="8;" graph[1][3]="0;" graph[1][4]="0;" graph[1][5]="11;" graph[1][6]="0;" graph[2][0]="0;" graph[2][1]="8;" graph[2][2]="0;" graph[2][3]="7;" graph[2][4]="0;" graph[2][5]="4;" graph[2][6]="0;" graph[3][0]="0;" graph[3][1]="0;" graph[3][2]="7;" graph[3][3]="0;" graph[3][4]="9;" graph[3][5]="14;" graph[3][6]="0;" graph[4][0]="0;" graph[4][1]="0;" graph[4][2]="0;" graph[4][3]="9;" graph[4][4]="0;" graph[4][5]="10;" graph[4][6]="2;" graph[5][0]="0;" graph[5][1]="0;" graph[5][2]="4;" graph[5][3]="14;" graph[5][4]="10;" graph[5][5]="0;" graph[5][6]="2;" graph[6][0]="0;" graph[6][1]="0;" graph[6][2]="0;" graph[6][3]="0;" graph[6][4]="2;" graph[6][5]="0;" graph[6][6]="1;" calling dijkstraalgorithm() by passing graph, number and dijkstraalgorithm(graph, source); return 0; pre> <p> <strong>Output</strong> </p> <pre> Distance from the Source Node to 1: 4 Distance from the Source Node to 2: 12 Distance from the Source Node to 3: 19 Distance from the Source Node to 4: 12 Distance from the Source Node to 5: 8 Distance from the Source Node to 6: 10 </pre> <p> <strong>Explanation:</strong> </p> <p>In the above snippet of code, we have included the <strong>stdio.h</strong> header file defined two constant values: <strong>INF = 9999</strong> and <strong>MAX = 10</strong> . We have declared the prototyping of the function and then defined the function for Dijkstra&apos;s Algorithm as <strong>DijkstraAlgorithm</strong> that accepts three arguments - the Graph consisting of the nodes, the number of nodes in the Graph, and the source node. Inside this function, we have defined some data structures such as a 2D matrix that will work as the Priority Queue for the algorithm, an array to main the distance between the nodes, an array to maintain the record of previous nodes, an array to store the visited nodes information, and some integer variables to store minimum distance value, counter, next node value and more. We then used a <strong>nested for-loop</strong> to iterate through the nodes of the Graph and add them to the priority queue accordingly. We have again used the <strong>for-loop</strong> to iterate through the elements in the priority queue starting from the source node and update their distances. Outside the loop, we have set the distance of the source node as <strong>0</strong> and marked it as visited in the <strong>visited_nodes[]</strong> array. We then set the counter value as one and used the <strong>while</strong> loop iterating through the number of nodes. Inside this loop, we have set the value of <strong>minimum_distance</strong> as <strong>INF</strong> and used the <strong>for-loop</strong> to update the value of the <strong>minimum_distance</strong> variable with the minimum value from a <strong>distance[]</strong> array. We then iterated through the unvisited neighboring nodes of the selected node using the <strong>for-loop</strong> and performed relaxation. We then printed the resulting data of the distances calculated using Dijkstra&apos;s Algorithm.</p> <p>In the <strong>main</strong> function, we have defined and declared the variables representing the Graph, the number of nodes, and the source node. At last, we have called the <strong>DijkstraAlgorithm()</strong> function by passing the required parameters.</p> <p>As a result, the required shortest possible paths for every node from the source node are printed for the users.</p> <h3>Code for Dijkstra&apos;s Algorithm in C++</h3> <p>The following is the implementation of Dijkstra&apos;s Algorithm in the C++ Programming Language:</p> <p> <strong>File: DijkstraAlgorithm.cpp</strong> </p> <pre> // Implementation of Dijkstra&apos;s Algorithm in C++ // importing the required header files #include #include // defining constant #define MAX_INT 10000000 // using the standard namespace using namespace std; // prototyping of the DijkstraAlgorithm() function void DijkstraAlgorithm(); // main function int main() { DijkstraAlgorithm(); return 0; } // declaring the classes class Vertex; class Edge; // prototyping the functions void Dijkstra(); vector* Adjacent_Remaining_Nodes(Vertex* vertex); Vertex* Extract_Smallest(vector&amp; vertices); int Distance(Vertex* vertexOne, Vertex* vertexTwo); bool Contains(vector&amp; vertices, Vertex* vertex); void Print_Shortest_Route_To(Vertex* des); // instantiating the classes vector vertices; vector edges; // defining the class for the vertices of the graph class Vertex { public: Vertex(char id) : id(id), prev(NULL), distance_from_start(MAX_INT) { vertices.push_back(this); } public: char id; Vertex* prev; int distance_from_start; }; // defining the class for the edges of the graph class Edge { public: Edge(Vertex* vertexOne, Vertex* vertexTwo, int distance) : vertexOne(vertexOne), vertexTwo(vertexTwo), distance(distance) { edges.push_back(this); } bool Connects(Vertex* vertexOne, Vertex* vertexTwo) public: Vertex* vertexOne; Vertex* vertexTwo; int distance; }; // defining the function to collect the details of the graph void DijkstraAlgorithm() { // declaring some vertices Vertex* vertex_a = new Vertex(&apos;A&apos;); Vertex* vertex_b = new Vertex(&apos;B&apos;); Vertex* vertex_c = new Vertex(&apos;C&apos;); Vertex* vertex_d = new Vertex(&apos;D&apos;); Vertex* vertex_e = new Vertex(&apos;E&apos;); Vertex* vertex_f = new Vertex(&apos;F&apos;); Vertex* vertex_g = new Vertex(&apos;G&apos;); // declaring some edges Edge* edge_1 = new Edge(vertex_a, vertex_c, 1); Edge* edge_2 = new Edge(vertex_a, vertex_d, 2); Edge* edge_3 = new Edge(vertex_b, vertex_c, 2); Edge* edge_4 = new Edge(vertex_c, vertex_d, 1); Edge* edge_5 = new Edge(vertex_b, vertex_f, 3); Edge* edge_6 = new Edge(vertex_c, vertex_e, 3); Edge* edge_7 = new Edge(vertex_e, vertex_f, 2); Edge* edge_8 = new Edge(vertex_d, vertex_g, 1); Edge* edge_9 = new Edge(vertex_g, vertex_f, 1); vertex_a -&gt; distance_from_start = 0; // setting a start vertex // calling the Dijkstra() function to find the shortest route possible Dijkstra(); // calling the Print_Shortest_Route_To() function to print the shortest route from the source vertex to the destination vertex Print_Shortest_Route_To(vertex_f); } // defining the function for Dijkstra&apos;s Algorithm void Dijkstra() { while (vertices.size() &gt; 0) { Vertex* smallest = Extract_Smallest(vertices); vector* adjacent_nodes = Adjacent_Remaining_Nodes(smallest); const int size = adjacent_nodes -&gt; size(); for (int i = 0; i at(i); int distance = Distance(smallest, adjacent) + smallest -&gt; distance_from_start; if (distance distance_from_start) { adjacent -&gt; distance_from_start = distance; adjacent -&gt; prev = smallest; } } delete adjacent_nodes; } } // defining the function to find the vertex with the shortest distance, removing it, and returning it Vertex* Extract_Smallest(vector&amp; vertices) { int size = vertices.size(); if (size == 0) return NULL; int smallest_position = 0; Vertex* smallest = vertices.at(0); for (int i = 1; i distance_from_start distance_from_start) { smallest = current; smallest_position = i; } } vertices.erase(vertices.begin() + smallest_position); return smallest; } // defining the function to return all vertices adjacent to &apos;vertex&apos; which are still in the &apos;vertices&apos; collection. vector* Adjacent_Remaining_Nodes(Vertex* vertex) { vector* adjacent_nodes = new vector(); const int size = edges.size(); for (int i = 0; i vertexOne == vertex) { adjacent = edge -&gt; vertexTwo; } else if (edge -&gt; vertexTwo == vertex) { adjacent = edge -&gt; vertexOne; } if (adjacent &amp;&amp; Contains(vertices, adjacent)) { adjacent_nodes -&gt; push_back(adjacent); } } return adjacent_nodes; } // defining the function to return distance between two connected vertices int Distance(Vertex* vertexOne, Vertex* vertexTwo) { const int size = edges.size(); for (int i = 0; i Connects(vertexOne, vertexTwo)) { return edge -&gt; distance; } } return -1; // should never happen } // defining the function to check if the &apos;vertices&apos; vector contains &apos;vertex&apos; bool Contains(vector&amp; vertices, Vertex* vertex) { const int size = vertices.size(); for (int i = 0; i <size; ++i) { if (vertex="=" vertices.at(i)) return true; } false; defining the function to print shortest route destination void print_shortest_route_to(vertex* des) vertex* prev="des;" cout << 'distance from start: ' < distance_from_start endl; while (prev) id prev; pre> <p> <strong>Output</strong> </p> <pre> Distance from start: 4 F G D A </pre> <p> <strong>Explanation:</strong> </p> <p>In the above code snippet, we included the <strong>&apos;iostream&apos;</strong> and <strong>&apos;vector&apos;</strong> header files and defined a constant value as <strong>MAX_INT = 10000000</strong> . We then used the standard namespace and prototyped the <strong>DijkstraAlgorithm()</strong> function. We then defined the main function of the program within, which we have called the <strong>DijkstraAlgorithm()</strong> function. After that, we declared some classes to create vertices and edges. We have also prototyped more functions to find the shortest possible path from the source vertex to the destination vertex and instantiated the Vertex and Edge classes. We then defined both classes to create the vertices and edges of the graph. We have then defined the <strong>DijkstraAlgorithm()</strong> function to create a graph and perform different operations. Inside this function, we have declared some vertices and edges. We then set the source vertex of the graph and called the <strong>Dijkstra()</strong> function to find the shortest possible distance and <strong>Print_Shortest_Route_To()</strong> function to print the shortest distance from the source vertex to vertex <strong>&apos;F&apos;</strong> . We have then defined the <strong>Dijkstra()</strong> function to calculate the shortest possible distances of the all the vertices from the source vertex. We have also defined some more functions to find the vertex with the shortest distance to return all the vertices adjacent to the remaining vertex, to return the distance between two connected vertices, to check if the selected vertex exists in the graph, and to print the shortest possible path from the source vertex to the destination vertex.</p> <p>As a result, the required shortest path for the vertex <strong>&apos;F&apos;</strong> from the source node is printed for the users.</p> <h3>Code for Dijkstra&apos;s Algorithm in Java</h3> <p>The following is the implementation of Dijkstra&apos;s Algorithm in the Java Programming Language:</p> <p> <strong>File: DijkstraAlgorithm.java</strong> </p> <pre> // Implementation of Dijkstra&apos;s Algorithm in Java // defining the public class for Dijkstra&apos;s Algorithm public class DijkstraAlgorithm { // defining the method to implement Dijkstra&apos;s Algorithm public void dijkstraAlgorithm(int[][] graph, int source) { // number of nodes int nodes = graph.length; boolean[] visited_vertex = new boolean[nodes]; int[] dist = new int[nodes]; for (int i = 0; i <nodes; 0 1 i++) { visited_vertex[i]="false;" dist[i]="Integer.MAX_VALUE;" } distance of self loop is zero dist[source]="0;" for (int i="0;" < nodes; updating the between neighboring vertex and source int u="find_min_distance(dist," visited_vertex); visited_vertex[u]="true;" distances all vertices v="0;" v++) if (!visited_vertex[v] && graph[u][v] !="0" (dist[u] + dist[v])) dist[v]="dist[u]" graph[u][v]; dist.length; system.out.println(string.format('distance from %s to %s', source, i, dist[i])); defining method find minimum private static find_min_distance(int[] dist, boolean[] visited_vertex) minimum_distance="Integer.MAX_VALUE;" minimum_distance_vertex="-1;" (!visited_vertex[i] minimum_distance) return minimum_distance_vertex; main function public void main(string[] args) declaring nodes graphs graph[][]="new" int[][] 0, 1, 2, }, 3, }; instantiating dijkstraalgorithm() class dijkstraalgorithm test="new" dijkstraalgorithm(); calling shortest node destination test.dijkstraalgorithm(graph, 0); pre> <p> <strong>Output</strong> </p> <pre> Distance from Vertex 0 to Vertex 0 is 0 Distance from Vertex 0 to Vertex 1 is 1 Distance from Vertex 0 to Vertex 2 is 1 Distance from Vertex 0 to Vertex 3 is 2 Distance from Vertex 0 to Vertex 4 is 4 Distance from Vertex 0 to Vertex 5 is 4 Distance from Vertex 0 to Vertex 6 is 3 </pre> <p> <strong>Explanation:</strong> </p> <p>In the above snippet of code, we have defined a public class as <strong>DijkstraAlgorithm()</strong> . Inside this class, we have defined a public method as <strong>dijkstraAlgorithm()</strong> to find the shortest distance from the source vertex to the destination vertex. Inside this method, we have defined a variable to store the number of nodes. We have then defined a Boolean array to store the information regarding the visited vertices and an integer array to store their respective distances. Initially, we declared the values in both the arrays as <strong>False</strong> and <strong>MAX_VALUE</strong> , respectively. We have also set the distance of the source vertex as zero and used the <strong>for-loop</strong> to update the distance between the source vertex and destination vertices with the minimum distance. We have then updated the distances of the neighboring vertices of the selected vertex by performing relaxation and printed the shortest distances for every vertex. We have then defined a method to find the minimum distance from the source vertex to the destination vertex. We then defined the main function where we declared the vertices of the graph and instantiated the <strong>DijkstraAlgorithm()</strong> class. Finally, we have called the <strong>dijkstraAlgorithm()</strong> method to find the shortest distance between the source vertex and the destination vertices.</p> <p>As a result, the required shortest possible paths for every node from the source node are printed for the users.</p> <h3>Code for Dijkstra&apos;s Algorithm in Python</h3> <p>The following is the implementation of Dijkstra&apos;s Algorithm in the Python Programming Language:</p> <p> <strong>File: DikstraAlgorithm.py</strong> </p> <pre> # Implementation of Dijkstra&apos;s Algorithm in Python # importing the sys module import sys # declaring the list of nodes for the graph nodes = [ [0, 0, 1, 0, 1, 0, 0], [0, 0, 1, 0, 0, 1, 0], [1, 1, 0, 1, 1, 0, 0], [1, 0, 1, 0, 0, 0, 1], [0, 0, 1, 0, 0, 1, 0], [0, 1, 0, 0, 1, 0, 1], [0, 0, 0, 1, 0, 1, 0] ] # declaring the list of edges for the graph edges = [ [0, 0, 1, 0, 2, 0, 0], [0, 0, 2, 0, 0, 3, 0], [1, 2, 0, 1, 3, 0, 0], [2, 0, 1, 0, 0, 0, 1], [0, 0, 3, 0, 0, 2, 0], [0, 3, 0, 0, 2, 0, 1], [0, 0, 0, 1, 0, 1, 0] ] # defining the function to find which node is to be visited next def toBeVisited(): global visitedAndDistance v = -10 for index in range(numberOfNodes): if visitedAndDistance[index][0] == 0 and (v <0 1 or visitedanddistance[index][1] <="visitedAndDistance[v][1]):" v="index" return # finding the number of nodes in graph numberofnodes="len(nodes[0])" visitedanddistance="[[0," 0]] for i range(numberofnodes - 1): visitedanddistance.append([0, sys.maxsize]) node range(numberofnodes): next to be visited tovisit="toBeVisited()" neighborindex updating new distances if nodes[tovisit][neighborindex]="=" and visitedanddistance[neighborindex][0]="=" 0: newdistance="visitedAndDistance[toVisit][1]" + edges[tovisit][neighborindex] visitedanddistance[neighborindex][1]> newDistance: visitedAndDistance[neighborIndex][1] = newDistance visitedAndDistance[toVisit][0] = 1 i = 0 # printing the distance for distance in visitedAndDistance: print(&apos;Distance of&apos;, chr(ord(&apos;A&apos;) + i), &apos;from source node:&apos;, distance[1]) i = i + 1 </0></pre> <p> <strong>Output</strong> </p> <pre> Distance of A from source node: 0 Distance of B from source node: 3 Distance of C from source node: 1 Distance of D from source node: 2 Distance of E from source node: 2 Distance of F from source node: 4 Distance of G from source node: 3 </pre> <p> <strong>Explanation:</strong> </p> <p>In the above snippet of code, we have imported the <strong>sys</strong> module and declared the lists consisting of the values for the nodes and edges. We have then defined a function as <strong>toBeVisited()</strong> to find which node will be visited next. We then found the total number of nodes in the graph and set the initial distances for every node. We have then calculated the minimum distance from the source node to the destination node, performed relaxation on neighboring nodes, and updated the distances in the list. We then printed those distances from the list for the users.</p> <p>As a result, the required shortest possible paths for every node from the source node are printed for the users.</p> <h2>Time and Space Complexity of Dijkstra&apos;s Algorithm</h2> <ul> <li>The Time Complexity of Dijkstra&apos;s Algorithm is <strong>O(E log V)</strong> , where E is the number of edges and V is the number of vertices.</li> <li>The Space Complexity of Dijkstra&apos;s Algorithm is O(V), where V is the number of vertices.</li> </ul> <h2>Advantages and Disadvantages of Dijkstra&apos;s Algorithm</h2> <p> <strong>Let us discuss some advantages of Dijkstra&apos;s Algorithm:</strong> </p> <ol class="points"> <li>One primary advantage of using Dijkstra&apos;s Algorithm is that it has an almost linear time and space complexity.</li> <li>We can use this algorithm to calculate the shortest path from a single vertex to all other vertices and a single source vertex to a single destination vertex by stopping the algorithm once we get the shortest distance for the destination vertex.</li> <li>This algorithm only works for directed weighted graphs, and all the edges of this graph should be non-negative.</li> </ol> <p> <strong>Despite having multiple advantages, Dijkstra&apos;s algorithm has some disadvantages also, such as:</strong> </p> <ol class="points"> <li>Dijkstra&apos;s Algorithm performs a concealed exploration that utilizes a lot of time during the process.</li> <li>This algorithm is impotent to handle negative edges.</li> <li>Since this algorithm heads to the acyclic graph, it cannot calculate the exact shortest path.</li> <li>It also requires maintenance to keep a record of vertices that have been visited.</li> </ol> <h2>Some Applications of Dijkstra&apos;s Algorithm</h2> <p> <strong>Dijkstra&apos;s Algorithm has various real-world applications, some of which are stated below:</strong> </p> <ol class="points"> <tr><td>Digital Mapping Services in Google Maps:</td> There are various times when we have tried to find the distance in Google Maps either from our location to the nearest preferred location or from one city to another, which comprises multiple routes/paths connecting them; however, the application must display the minimum distance. This is only possible because Dijkstra&apos;s algorithm helps the application find the shortest between two given locations along the path. Let us consider the USA as a graph wherein the cities/places are represented as vertices, and the routes between two cities/places are represented as edges. Then with the help of Dijkstra&apos;s Algorithm, we can calculate the shortest routes between any two cities/places. </tr><tr><td>Social Networking Applications:</td> In many applications like Facebook, Twitter, Instagram, and more, many of us might have observed that these apps suggest the list of friends that a specific user may know. How do many social media companies implement this type of feature in an efficient and effective way, specifically when the system has over a billion users? The answer to this question is Dijkstra&apos;s Algorithm. The standard Dijkstra&apos;s Algorithm is generally used to estimate the shortest distance between the users measured through the connections or mutuality among them. When social networking is very small, it uses the standard Dijkstra&apos;s Algorithm in addition to some other features in order to determine the shortest paths. However, when the graph is much bigger, the standard algorithm takes several seconds to count, and thus, some advanced algorithms are used as the alternative. </tr><tr><td>Telephone Network:</td> As some of us might know, in a telephone network, each transmission line has a bandwidth, &apos;b&apos;. The bandwidth is the highest frequency that the transmission line can support. In general, if the frequency of the signal is higher in a specific line, the signal is reduced by that line. Bandwidth represents the amount of information that can be transmitted by the line. Let us consider a city a graph wherein the switching stations are represented using the vertices, the transmission lines are represented as the edges, and the bandwidth, &apos;b&apos;, is represented using the weight of the edges. Thus, as we can observe, the telephone network can also fall into the category of the shortest distance problem and can be solved using Dijkstra&apos;s Algorithm. </tr><tr><td>Flight Program:</td> Suppose that a person requires software to prepare an agenda of flights for customers. The agent has access to a database with all flights and airports. In addition to the flight number, origin airport, and destination, the flights also have departure and arrival times. So, in order to determine the earliest arrival time for the selected destination from the original airport and given start time, the agents make use of Dijkstra&apos;s Algorithm. </tr><tr><td>IP routing to find Open Shortest Path First:</td> Open Shortest Path First (abbreviated as OSPF) is a link-state routing protocol used to find the best path between the source and destination router with the help of its own Shortest Path First. Dijkstra&apos;s Algorithm is extensively utilized in the routing protocols required by the routers in order to update their forwarding table. The algorithm gives the shortest cost path from the source router to the other routers present in the network. </tr><tr><td>Robotic Path:</td> These days, drones and robots have come into existence, some operated manually and some automatically. The drones and robots which are operated automatically and used to deliver the packages to a given location or used for any certain task are configured with Dijkstra&apos;s Algorithm module so that whenever the source and destination are known, the drone and robot will move in the ordered direction by following the shortest path keeping the time taken to a minimum in order to deliver the packages. </tr><tr><td>Designate the File Server:</td> Dijkstra&apos;s Algorithm is also used to designate a file server in a Local Area Network (LAN). Suppose that an infinite period of time is needed for the transmission of the files from one computer to another. So, to minimize the number of &apos;hops&apos; from the file server to every other computer on the network, we will use Dijkstra&apos;s Algorithm. This algorithm will return the shortest path between the networks resulting in the minimum number of hops. </tr></ol> <h2>The Conclusion</h2> <ul> <li>In the above tutorial, firstly, we have understood the basic concepts of Graph along with its types and applications.</li> <li>We then learned about Dijkstra&apos;s Algorithm and its history.</li> <li>We have also understood the fundamental working of Dijkstra&apos;s Algorithm with the help of an example.</li> <li>After that, we studied how to write code for Dijkstra&apos;s Algorithm with the help of Pseudocode.</li> <li>We observed its implementation in programming languages like C, C++, Java, and Python with proper outputs and explanations.</li> <li>We have also understood the Time and Space Complexity of Dijkstra&apos;s Algorithm.</li> <li>Finally, we have discussed the advantages and disadvantages of Dijkstra&apos;s algorithm and some of its real-life applications.</li> </ul> <hr></nodes;></pre></size;></pre></size;></pre></distance[n]>

توضيح:

في مقتطف التعليمات البرمجية أعلاه، قمنا بتضمين stdio.h حدد ملف الرأس قيمتين ثابتتين: المعلومات = 9999 و الحد الأقصى = 10 . لقد أعلنا عن النماذج الأولية للوظيفة ثم حددنا وظيفة خوارزمية Dijkstra على أنها خوارزمية ديكسترا يقبل ثلاث وسيطات - الرسم البياني الذي يتكون من العقد، وعدد العقد في الرسم البياني، والعقدة المصدر. داخل هذه الوظيفة، قمنا بتعريف بعض هياكل البيانات مثل مصفوفة ثنائية الأبعاد التي ستعمل كقائمة انتظار الأولوية للخوارزمية، ومصفوفة لتوجيه المسافة بين العقد، ومصفوفة للحفاظ على سجل العقد السابقة، ومصفوفة لتخزين معلومات العقد التي تمت زيارتها وبعض المتغيرات الصحيحة لتخزين الحد الأدنى لقيمة المسافة والعداد وقيمة العقدة التالية والمزيد. ثم استخدمنا أ متداخلة للحلقة للتكرار عبر عقد الرسم البياني وإضافتها إلى قائمة انتظار الأولوية وفقًا لذلك. لقد استخدمنا مرة أخرى لحلقة للتكرار عبر العناصر الموجودة في قائمة انتظار الأولوية بدءًا من العقدة المصدر وتحديث مسافاتها. خارج الحلقة، قمنا بتعيين مسافة العقدة المصدر كما 0 ووضع علامة عليها كما تمت زيارتها في تمت زيارة العقد[] مجموعة مصفوفة. ثم قمنا بتعيين قيمة العداد كواحد واستخدمنا بينما حلقة التكرار من خلال عدد العقد. داخل هذه الحلقة، قمنا بتعيين قيمة الحد الأدنى_المسافة مثل الوقود النووي المشع واستخدمت لحلقة لتحديث قيمة الحد الأدنى_المسافة متغير مع الحد الأدنى من القيمة من أ مسافة[] مجموعة مصفوفة. قمنا بعد ذلك بالتكرار عبر العقد المجاورة غير التي تمت زيارتها للعقدة المحددة باستخدام ملف لحلقة وأدى الاسترخاء. قمنا بعد ذلك بطباعة البيانات الناتجة للمسافات المحسوبة باستخدام خوارزمية ديكسترا.

في ال رئيسي دالة، قمنا بتعريف وإعلان المتغيرات التي تمثل الرسم البياني، وعدد العقد، والعقدة المصدر. أخيرًا، اتصلنا بـ خوارزمية ديكسترا () وظيفة عن طريق تمرير المعلمات المطلوبة.

ونتيجة لذلك، تتم طباعة أقصر المسارات الممكنة المطلوبة لكل عقدة من العقدة المصدر للمستخدمين.

كود خوارزمية Dijkstra في لغة C++

فيما يلي تنفيذ خوارزمية Dijkstra في لغة البرمجة C++:

ملف: DijkstraAlgorithm.cpp

 // Implementation of Dijkstra&apos;s Algorithm in C++ // importing the required header files #include #include // defining constant #define MAX_INT 10000000 // using the standard namespace using namespace std; // prototyping of the DijkstraAlgorithm() function void DijkstraAlgorithm(); // main function int main() { DijkstraAlgorithm(); return 0; } // declaring the classes class Vertex; class Edge; // prototyping the functions void Dijkstra(); vector* Adjacent_Remaining_Nodes(Vertex* vertex); Vertex* Extract_Smallest(vector&amp; vertices); int Distance(Vertex* vertexOne, Vertex* vertexTwo); bool Contains(vector&amp; vertices, Vertex* vertex); void Print_Shortest_Route_To(Vertex* des); // instantiating the classes vector vertices; vector edges; // defining the class for the vertices of the graph class Vertex { public: Vertex(char id) : id(id), prev(NULL), distance_from_start(MAX_INT) { vertices.push_back(this); } public: char id; Vertex* prev; int distance_from_start; }; // defining the class for the edges of the graph class Edge { public: Edge(Vertex* vertexOne, Vertex* vertexTwo, int distance) : vertexOne(vertexOne), vertexTwo(vertexTwo), distance(distance) { edges.push_back(this); } bool Connects(Vertex* vertexOne, Vertex* vertexTwo) public: Vertex* vertexOne; Vertex* vertexTwo; int distance; }; // defining the function to collect the details of the graph void DijkstraAlgorithm() { // declaring some vertices Vertex* vertex_a = new Vertex(&apos;A&apos;); Vertex* vertex_b = new Vertex(&apos;B&apos;); Vertex* vertex_c = new Vertex(&apos;C&apos;); Vertex* vertex_d = new Vertex(&apos;D&apos;); Vertex* vertex_e = new Vertex(&apos;E&apos;); Vertex* vertex_f = new Vertex(&apos;F&apos;); Vertex* vertex_g = new Vertex(&apos;G&apos;); // declaring some edges Edge* edge_1 = new Edge(vertex_a, vertex_c, 1); Edge* edge_2 = new Edge(vertex_a, vertex_d, 2); Edge* edge_3 = new Edge(vertex_b, vertex_c, 2); Edge* edge_4 = new Edge(vertex_c, vertex_d, 1); Edge* edge_5 = new Edge(vertex_b, vertex_f, 3); Edge* edge_6 = new Edge(vertex_c, vertex_e, 3); Edge* edge_7 = new Edge(vertex_e, vertex_f, 2); Edge* edge_8 = new Edge(vertex_d, vertex_g, 1); Edge* edge_9 = new Edge(vertex_g, vertex_f, 1); vertex_a -&gt; distance_from_start = 0; // setting a start vertex // calling the Dijkstra() function to find the shortest route possible Dijkstra(); // calling the Print_Shortest_Route_To() function to print the shortest route from the source vertex to the destination vertex Print_Shortest_Route_To(vertex_f); } // defining the function for Dijkstra&apos;s Algorithm void Dijkstra() { while (vertices.size() &gt; 0) { Vertex* smallest = Extract_Smallest(vertices); vector* adjacent_nodes = Adjacent_Remaining_Nodes(smallest); const int size = adjacent_nodes -&gt; size(); for (int i = 0; i at(i); int distance = Distance(smallest, adjacent) + smallest -&gt; distance_from_start; if (distance distance_from_start) { adjacent -&gt; distance_from_start = distance; adjacent -&gt; prev = smallest; } } delete adjacent_nodes; } } // defining the function to find the vertex with the shortest distance, removing it, and returning it Vertex* Extract_Smallest(vector&amp; vertices) { int size = vertices.size(); if (size == 0) return NULL; int smallest_position = 0; Vertex* smallest = vertices.at(0); for (int i = 1; i distance_from_start distance_from_start) { smallest = current; smallest_position = i; } } vertices.erase(vertices.begin() + smallest_position); return smallest; } // defining the function to return all vertices adjacent to &apos;vertex&apos; which are still in the &apos;vertices&apos; collection. vector* Adjacent_Remaining_Nodes(Vertex* vertex) { vector* adjacent_nodes = new vector(); const int size = edges.size(); for (int i = 0; i vertexOne == vertex) { adjacent = edge -&gt; vertexTwo; } else if (edge -&gt; vertexTwo == vertex) { adjacent = edge -&gt; vertexOne; } if (adjacent &amp;&amp; Contains(vertices, adjacent)) { adjacent_nodes -&gt; push_back(adjacent); } } return adjacent_nodes; } // defining the function to return distance between two connected vertices int Distance(Vertex* vertexOne, Vertex* vertexTwo) { const int size = edges.size(); for (int i = 0; i Connects(vertexOne, vertexTwo)) { return edge -&gt; distance; } } return -1; // should never happen } // defining the function to check if the &apos;vertices&apos; vector contains &apos;vertex&apos; bool Contains(vector&amp; vertices, Vertex* vertex) { const int size = vertices.size(); for (int i = 0; i <size; ++i) { if (vertex="=" vertices.at(i)) return true; } false; defining the function to print shortest route destination void print_shortest_route_to(vertex* des) vertex* prev="des;" cout << \'distance from start: \' < distance_from_start endl; while (prev) id prev; pre> <p> <strong>Output</strong> </p> <pre> Distance from start: 4 F G D A </pre> <p> <strong>Explanation:</strong> </p> <p>In the above code snippet, we included the <strong>&apos;iostream&apos;</strong> and <strong>&apos;vector&apos;</strong> header files and defined a constant value as <strong>MAX_INT = 10000000</strong> . We then used the standard namespace and prototyped the <strong>DijkstraAlgorithm()</strong> function. We then defined the main function of the program within, which we have called the <strong>DijkstraAlgorithm()</strong> function. After that, we declared some classes to create vertices and edges. We have also prototyped more functions to find the shortest possible path from the source vertex to the destination vertex and instantiated the Vertex and Edge classes. We then defined both classes to create the vertices and edges of the graph. We have then defined the <strong>DijkstraAlgorithm()</strong> function to create a graph and perform different operations. Inside this function, we have declared some vertices and edges. We then set the source vertex of the graph and called the <strong>Dijkstra()</strong> function to find the shortest possible distance and <strong>Print_Shortest_Route_To()</strong> function to print the shortest distance from the source vertex to vertex <strong>&apos;F&apos;</strong> . We have then defined the <strong>Dijkstra()</strong> function to calculate the shortest possible distances of the all the vertices from the source vertex. We have also defined some more functions to find the vertex with the shortest distance to return all the vertices adjacent to the remaining vertex, to return the distance between two connected vertices, to check if the selected vertex exists in the graph, and to print the shortest possible path from the source vertex to the destination vertex.</p> <p>As a result, the required shortest path for the vertex <strong>&apos;F&apos;</strong> from the source node is printed for the users.</p> <h3>Code for Dijkstra&apos;s Algorithm in Java</h3> <p>The following is the implementation of Dijkstra&apos;s Algorithm in the Java Programming Language:</p> <p> <strong>File: DijkstraAlgorithm.java</strong> </p> <pre> // Implementation of Dijkstra&apos;s Algorithm in Java // defining the public class for Dijkstra&apos;s Algorithm public class DijkstraAlgorithm { // defining the method to implement Dijkstra&apos;s Algorithm public void dijkstraAlgorithm(int[][] graph, int source) { // number of nodes int nodes = graph.length; boolean[] visited_vertex = new boolean[nodes]; int[] dist = new int[nodes]; for (int i = 0; i <nodes; 0 1 i++) { visited_vertex[i]="false;" dist[i]="Integer.MAX_VALUE;" } distance of self loop is zero dist[source]="0;" for (int i="0;" < nodes; updating the between neighboring vertex and source int u="find_min_distance(dist," visited_vertex); visited_vertex[u]="true;" distances all vertices v="0;" v++) if (!visited_vertex[v] && graph[u][v] !="0" (dist[u] + dist[v])) dist[v]="dist[u]" graph[u][v]; dist.length; system.out.println(string.format(\'distance from %s to %s\', source, i, dist[i])); defining method find minimum private static find_min_distance(int[] dist, boolean[] visited_vertex) minimum_distance="Integer.MAX_VALUE;" minimum_distance_vertex="-1;" (!visited_vertex[i] minimum_distance) return minimum_distance_vertex; main function public void main(string[] args) declaring nodes graphs graph[][]="new" int[][] 0, 1, 2, }, 3, }; instantiating dijkstraalgorithm() class dijkstraalgorithm test="new" dijkstraalgorithm(); calling shortest node destination test.dijkstraalgorithm(graph, 0); pre> <p> <strong>Output</strong> </p> <pre> Distance from Vertex 0 to Vertex 0 is 0 Distance from Vertex 0 to Vertex 1 is 1 Distance from Vertex 0 to Vertex 2 is 1 Distance from Vertex 0 to Vertex 3 is 2 Distance from Vertex 0 to Vertex 4 is 4 Distance from Vertex 0 to Vertex 5 is 4 Distance from Vertex 0 to Vertex 6 is 3 </pre> <p> <strong>Explanation:</strong> </p> <p>In the above snippet of code, we have defined a public class as <strong>DijkstraAlgorithm()</strong> . Inside this class, we have defined a public method as <strong>dijkstraAlgorithm()</strong> to find the shortest distance from the source vertex to the destination vertex. Inside this method, we have defined a variable to store the number of nodes. We have then defined a Boolean array to store the information regarding the visited vertices and an integer array to store their respective distances. Initially, we declared the values in both the arrays as <strong>False</strong> and <strong>MAX_VALUE</strong> , respectively. We have also set the distance of the source vertex as zero and used the <strong>for-loop</strong> to update the distance between the source vertex and destination vertices with the minimum distance. We have then updated the distances of the neighboring vertices of the selected vertex by performing relaxation and printed the shortest distances for every vertex. We have then defined a method to find the minimum distance from the source vertex to the destination vertex. We then defined the main function where we declared the vertices of the graph and instantiated the <strong>DijkstraAlgorithm()</strong> class. Finally, we have called the <strong>dijkstraAlgorithm()</strong> method to find the shortest distance between the source vertex and the destination vertices.</p> <p>As a result, the required shortest possible paths for every node from the source node are printed for the users.</p> <h3>Code for Dijkstra&apos;s Algorithm in Python</h3> <p>The following is the implementation of Dijkstra&apos;s Algorithm in the Python Programming Language:</p> <p> <strong>File: DikstraAlgorithm.py</strong> </p> <pre> # Implementation of Dijkstra&apos;s Algorithm in Python # importing the sys module import sys # declaring the list of nodes for the graph nodes = [ [0, 0, 1, 0, 1, 0, 0], [0, 0, 1, 0, 0, 1, 0], [1, 1, 0, 1, 1, 0, 0], [1, 0, 1, 0, 0, 0, 1], [0, 0, 1, 0, 0, 1, 0], [0, 1, 0, 0, 1, 0, 1], [0, 0, 0, 1, 0, 1, 0] ] # declaring the list of edges for the graph edges = [ [0, 0, 1, 0, 2, 0, 0], [0, 0, 2, 0, 0, 3, 0], [1, 2, 0, 1, 3, 0, 0], [2, 0, 1, 0, 0, 0, 1], [0, 0, 3, 0, 0, 2, 0], [0, 3, 0, 0, 2, 0, 1], [0, 0, 0, 1, 0, 1, 0] ] # defining the function to find which node is to be visited next def toBeVisited(): global visitedAndDistance v = -10 for index in range(numberOfNodes): if visitedAndDistance[index][0] == 0 and (v <0 1 or visitedanddistance[index][1] <="visitedAndDistance[v][1]):" v="index" return # finding the number of nodes in graph numberofnodes="len(nodes[0])" visitedanddistance="[[0," 0]] for i range(numberofnodes - 1): visitedanddistance.append([0, sys.maxsize]) node range(numberofnodes): next to be visited tovisit="toBeVisited()" neighborindex updating new distances if nodes[tovisit][neighborindex]="=" and visitedanddistance[neighborindex][0]="=" 0: newdistance="visitedAndDistance[toVisit][1]" + edges[tovisit][neighborindex] visitedanddistance[neighborindex][1]> newDistance: visitedAndDistance[neighborIndex][1] = newDistance visitedAndDistance[toVisit][0] = 1 i = 0 # printing the distance for distance in visitedAndDistance: print(&apos;Distance of&apos;, chr(ord(&apos;A&apos;) + i), &apos;from source node:&apos;, distance[1]) i = i + 1 </0></pre> <p> <strong>Output</strong> </p> <pre> Distance of A from source node: 0 Distance of B from source node: 3 Distance of C from source node: 1 Distance of D from source node: 2 Distance of E from source node: 2 Distance of F from source node: 4 Distance of G from source node: 3 </pre> <p> <strong>Explanation:</strong> </p> <p>In the above snippet of code, we have imported the <strong>sys</strong> module and declared the lists consisting of the values for the nodes and edges. We have then defined a function as <strong>toBeVisited()</strong> to find which node will be visited next. We then found the total number of nodes in the graph and set the initial distances for every node. We have then calculated the minimum distance from the source node to the destination node, performed relaxation on neighboring nodes, and updated the distances in the list. We then printed those distances from the list for the users.</p> <p>As a result, the required shortest possible paths for every node from the source node are printed for the users.</p> <h2>Time and Space Complexity of Dijkstra&apos;s Algorithm</h2> <ul> <li>The Time Complexity of Dijkstra&apos;s Algorithm is <strong>O(E log V)</strong> , where E is the number of edges and V is the number of vertices.</li> <li>The Space Complexity of Dijkstra&apos;s Algorithm is O(V), where V is the number of vertices.</li> </ul> <h2>Advantages and Disadvantages of Dijkstra&apos;s Algorithm</h2> <p> <strong>Let us discuss some advantages of Dijkstra&apos;s Algorithm:</strong> </p> <ol class="points"> <li>One primary advantage of using Dijkstra&apos;s Algorithm is that it has an almost linear time and space complexity.</li> <li>We can use this algorithm to calculate the shortest path from a single vertex to all other vertices and a single source vertex to a single destination vertex by stopping the algorithm once we get the shortest distance for the destination vertex.</li> <li>This algorithm only works for directed weighted graphs, and all the edges of this graph should be non-negative.</li> </ol> <p> <strong>Despite having multiple advantages, Dijkstra&apos;s algorithm has some disadvantages also, such as:</strong> </p> <ol class="points"> <li>Dijkstra&apos;s Algorithm performs a concealed exploration that utilizes a lot of time during the process.</li> <li>This algorithm is impotent to handle negative edges.</li> <li>Since this algorithm heads to the acyclic graph, it cannot calculate the exact shortest path.</li> <li>It also requires maintenance to keep a record of vertices that have been visited.</li> </ol> <h2>Some Applications of Dijkstra&apos;s Algorithm</h2> <p> <strong>Dijkstra&apos;s Algorithm has various real-world applications, some of which are stated below:</strong> </p> <ol class="points"> <tr><td>Digital Mapping Services in Google Maps:</td> There are various times when we have tried to find the distance in Google Maps either from our location to the nearest preferred location or from one city to another, which comprises multiple routes/paths connecting them; however, the application must display the minimum distance. This is only possible because Dijkstra&apos;s algorithm helps the application find the shortest between two given locations along the path. Let us consider the USA as a graph wherein the cities/places are represented as vertices, and the routes between two cities/places are represented as edges. Then with the help of Dijkstra&apos;s Algorithm, we can calculate the shortest routes between any two cities/places. </tr><tr><td>Social Networking Applications:</td> In many applications like Facebook, Twitter, Instagram, and more, many of us might have observed that these apps suggest the list of friends that a specific user may know. How do many social media companies implement this type of feature in an efficient and effective way, specifically when the system has over a billion users? The answer to this question is Dijkstra&apos;s Algorithm. The standard Dijkstra&apos;s Algorithm is generally used to estimate the shortest distance between the users measured through the connections or mutuality among them. When social networking is very small, it uses the standard Dijkstra&apos;s Algorithm in addition to some other features in order to determine the shortest paths. However, when the graph is much bigger, the standard algorithm takes several seconds to count, and thus, some advanced algorithms are used as the alternative. </tr><tr><td>Telephone Network:</td> As some of us might know, in a telephone network, each transmission line has a bandwidth, &apos;b&apos;. The bandwidth is the highest frequency that the transmission line can support. In general, if the frequency of the signal is higher in a specific line, the signal is reduced by that line. Bandwidth represents the amount of information that can be transmitted by the line. Let us consider a city a graph wherein the switching stations are represented using the vertices, the transmission lines are represented as the edges, and the bandwidth, &apos;b&apos;, is represented using the weight of the edges. Thus, as we can observe, the telephone network can also fall into the category of the shortest distance problem and can be solved using Dijkstra&apos;s Algorithm. </tr><tr><td>Flight Program:</td> Suppose that a person requires software to prepare an agenda of flights for customers. The agent has access to a database with all flights and airports. In addition to the flight number, origin airport, and destination, the flights also have departure and arrival times. So, in order to determine the earliest arrival time for the selected destination from the original airport and given start time, the agents make use of Dijkstra&apos;s Algorithm. </tr><tr><td>IP routing to find Open Shortest Path First:</td> Open Shortest Path First (abbreviated as OSPF) is a link-state routing protocol used to find the best path between the source and destination router with the help of its own Shortest Path First. Dijkstra&apos;s Algorithm is extensively utilized in the routing protocols required by the routers in order to update their forwarding table. The algorithm gives the shortest cost path from the source router to the other routers present in the network. </tr><tr><td>Robotic Path:</td> These days, drones and robots have come into existence, some operated manually and some automatically. The drones and robots which are operated automatically and used to deliver the packages to a given location or used for any certain task are configured with Dijkstra&apos;s Algorithm module so that whenever the source and destination are known, the drone and robot will move in the ordered direction by following the shortest path keeping the time taken to a minimum in order to deliver the packages. </tr><tr><td>Designate the File Server:</td> Dijkstra&apos;s Algorithm is also used to designate a file server in a Local Area Network (LAN). Suppose that an infinite period of time is needed for the transmission of the files from one computer to another. So, to minimize the number of &apos;hops&apos; from the file server to every other computer on the network, we will use Dijkstra&apos;s Algorithm. This algorithm will return the shortest path between the networks resulting in the minimum number of hops. </tr></ol> <h2>The Conclusion</h2> <ul> <li>In the above tutorial, firstly, we have understood the basic concepts of Graph along with its types and applications.</li> <li>We then learned about Dijkstra&apos;s Algorithm and its history.</li> <li>We have also understood the fundamental working of Dijkstra&apos;s Algorithm with the help of an example.</li> <li>After that, we studied how to write code for Dijkstra&apos;s Algorithm with the help of Pseudocode.</li> <li>We observed its implementation in programming languages like C, C++, Java, and Python with proper outputs and explanations.</li> <li>We have also understood the Time and Space Complexity of Dijkstra&apos;s Algorithm.</li> <li>Finally, we have discussed the advantages and disadvantages of Dijkstra&apos;s algorithm and some of its real-life applications.</li> </ul> <hr></nodes;></pre></size;>

توضيح:

في مقتطف الكود أعلاه، قمنا بتضمين 'iostream' و 'المتجه' ملفات الرأس وحدد قيمة ثابتة كـ MAX_INT = 10000000 . استخدمنا بعد ذلك مساحة الاسم القياسية وقمنا بإنشاء نموذج أولي لـ خوارزمية ديكسترا () وظيفة. ثم قمنا بتحديد الوظيفة الرئيسية للبرنامج، والتي أطلقنا عليها اسم خوارزمية ديكسترا () وظيفة. بعد ذلك، قمنا بإعلان بعض الفئات لإنشاء القمم والحواف. لقد قمنا أيضًا بإنشاء نماذج أولية لمزيد من الوظائف للعثور على أقصر مسار ممكن من قمة المصدر إلى قمة الوجهة وقمنا بإنشاء مثيل لفئتي Vertex وEdge. ثم قمنا بتعريف كلا الفئتين لإنشاء رؤوس وحواف الرسم البياني. لقد قمنا بعد ذلك بتعريف خوارزمية ديكسترا () وظيفة لإنشاء رسم بياني وتنفيذ عمليات مختلفة. داخل هذه الدالة، أعلنا عن بعض القمم والحواف. ثم قمنا بتعيين قمة المصدر للرسم البياني وأطلقنا عليها اسم ديكسترا() وظيفة للعثور على أقصر مسافة ممكنة و Print_Shortest_Route_To() وظيفة لطباعة أقصر مسافة من قمة المصدر إلى قمة الرأس 'F' . لقد قمنا بعد ذلك بتعريف ديكسترا() دالة لحساب أقصر مسافة ممكنة لجميع القمم من قمة المصدر. لقد حددنا أيضًا بعض الوظائف الإضافية للعثور على الرأس بأقصر مسافة لإرجاع جميع القمم المجاورة للرأس المتبقي، ولإرجاع المسافة بين رأسين متصلين، وللتحقق من وجود الرأس المحدد في الرسم البياني، ولطباعة أقصر مسار ممكن من قمة المصدر إلى قمة الوجهة.

يمكن لفئة تمديد فئات متعددة

ونتيجة لذلك، أقصر مسار مطلوب للقمة 'F' من العقدة المصدر تتم طباعتها للمستخدمين.

كود خوارزمية ديكسترا في جافا

وفيما يلي تنفيذ خوارزمية ديكسترا في لغة برمجة جافا:

الملف: DijkstraAlgorithm.java

 // Implementation of Dijkstra&apos;s Algorithm in Java // defining the public class for Dijkstra&apos;s Algorithm public class DijkstraAlgorithm { // defining the method to implement Dijkstra&apos;s Algorithm public void dijkstraAlgorithm(int[][] graph, int source) { // number of nodes int nodes = graph.length; boolean[] visited_vertex = new boolean[nodes]; int[] dist = new int[nodes]; for (int i = 0; i <nodes; 0 1 i++) { visited_vertex[i]="false;" dist[i]="Integer.MAX_VALUE;" } distance of self loop is zero dist[source]="0;" for (int i="0;" < nodes; updating the between neighboring vertex and source int u="find_min_distance(dist," visited_vertex); visited_vertex[u]="true;" distances all vertices v="0;" v++) if (!visited_vertex[v] && graph[u][v] !="0" (dist[u] + dist[v])) dist[v]="dist[u]" graph[u][v]; dist.length; system.out.println(string.format(\'distance from %s to %s\', source, i, dist[i])); defining method find minimum private static find_min_distance(int[] dist, boolean[] visited_vertex) minimum_distance="Integer.MAX_VALUE;" minimum_distance_vertex="-1;" (!visited_vertex[i] minimum_distance) return minimum_distance_vertex; main function public void main(string[] args) declaring nodes graphs graph[][]="new" int[][] 0, 1, 2, }, 3, }; instantiating dijkstraalgorithm() class dijkstraalgorithm test="new" dijkstraalgorithm(); calling shortest node destination test.dijkstraalgorithm(graph, 0); pre> <p> <strong>Output</strong> </p> <pre> Distance from Vertex 0 to Vertex 0 is 0 Distance from Vertex 0 to Vertex 1 is 1 Distance from Vertex 0 to Vertex 2 is 1 Distance from Vertex 0 to Vertex 3 is 2 Distance from Vertex 0 to Vertex 4 is 4 Distance from Vertex 0 to Vertex 5 is 4 Distance from Vertex 0 to Vertex 6 is 3 </pre> <p> <strong>Explanation:</strong> </p> <p>In the above snippet of code, we have defined a public class as <strong>DijkstraAlgorithm()</strong> . Inside this class, we have defined a public method as <strong>dijkstraAlgorithm()</strong> to find the shortest distance from the source vertex to the destination vertex. Inside this method, we have defined a variable to store the number of nodes. We have then defined a Boolean array to store the information regarding the visited vertices and an integer array to store their respective distances. Initially, we declared the values in both the arrays as <strong>False</strong> and <strong>MAX_VALUE</strong> , respectively. We have also set the distance of the source vertex as zero and used the <strong>for-loop</strong> to update the distance between the source vertex and destination vertices with the minimum distance. We have then updated the distances of the neighboring vertices of the selected vertex by performing relaxation and printed the shortest distances for every vertex. We have then defined a method to find the minimum distance from the source vertex to the destination vertex. We then defined the main function where we declared the vertices of the graph and instantiated the <strong>DijkstraAlgorithm()</strong> class. Finally, we have called the <strong>dijkstraAlgorithm()</strong> method to find the shortest distance between the source vertex and the destination vertices.</p> <p>As a result, the required shortest possible paths for every node from the source node are printed for the users.</p> <h3>Code for Dijkstra&apos;s Algorithm in Python</h3> <p>The following is the implementation of Dijkstra&apos;s Algorithm in the Python Programming Language:</p> <p> <strong>File: DikstraAlgorithm.py</strong> </p> <pre> # Implementation of Dijkstra&apos;s Algorithm in Python # importing the sys module import sys # declaring the list of nodes for the graph nodes = [ [0, 0, 1, 0, 1, 0, 0], [0, 0, 1, 0, 0, 1, 0], [1, 1, 0, 1, 1, 0, 0], [1, 0, 1, 0, 0, 0, 1], [0, 0, 1, 0, 0, 1, 0], [0, 1, 0, 0, 1, 0, 1], [0, 0, 0, 1, 0, 1, 0] ] # declaring the list of edges for the graph edges = [ [0, 0, 1, 0, 2, 0, 0], [0, 0, 2, 0, 0, 3, 0], [1, 2, 0, 1, 3, 0, 0], [2, 0, 1, 0, 0, 0, 1], [0, 0, 3, 0, 0, 2, 0], [0, 3, 0, 0, 2, 0, 1], [0, 0, 0, 1, 0, 1, 0] ] # defining the function to find which node is to be visited next def toBeVisited(): global visitedAndDistance v = -10 for index in range(numberOfNodes): if visitedAndDistance[index][0] == 0 and (v <0 1 or visitedanddistance[index][1] <="visitedAndDistance[v][1]):" v="index" return # finding the number of nodes in graph numberofnodes="len(nodes[0])" visitedanddistance="[[0," 0]] for i range(numberofnodes - 1): visitedanddistance.append([0, sys.maxsize]) node range(numberofnodes): next to be visited tovisit="toBeVisited()" neighborindex updating new distances if nodes[tovisit][neighborindex]="=" and visitedanddistance[neighborindex][0]="=" 0: newdistance="visitedAndDistance[toVisit][1]" + edges[tovisit][neighborindex] visitedanddistance[neighborindex][1]> newDistance: visitedAndDistance[neighborIndex][1] = newDistance visitedAndDistance[toVisit][0] = 1 i = 0 # printing the distance for distance in visitedAndDistance: print(&apos;Distance of&apos;, chr(ord(&apos;A&apos;) + i), &apos;from source node:&apos;, distance[1]) i = i + 1 </0></pre> <p> <strong>Output</strong> </p> <pre> Distance of A from source node: 0 Distance of B from source node: 3 Distance of C from source node: 1 Distance of D from source node: 2 Distance of E from source node: 2 Distance of F from source node: 4 Distance of G from source node: 3 </pre> <p> <strong>Explanation:</strong> </p> <p>In the above snippet of code, we have imported the <strong>sys</strong> module and declared the lists consisting of the values for the nodes and edges. We have then defined a function as <strong>toBeVisited()</strong> to find which node will be visited next. We then found the total number of nodes in the graph and set the initial distances for every node. We have then calculated the minimum distance from the source node to the destination node, performed relaxation on neighboring nodes, and updated the distances in the list. We then printed those distances from the list for the users.</p> <p>As a result, the required shortest possible paths for every node from the source node are printed for the users.</p> <h2>Time and Space Complexity of Dijkstra&apos;s Algorithm</h2> <ul> <li>The Time Complexity of Dijkstra&apos;s Algorithm is <strong>O(E log V)</strong> , where E is the number of edges and V is the number of vertices.</li> <li>The Space Complexity of Dijkstra&apos;s Algorithm is O(V), where V is the number of vertices.</li> </ul> <h2>Advantages and Disadvantages of Dijkstra&apos;s Algorithm</h2> <p> <strong>Let us discuss some advantages of Dijkstra&apos;s Algorithm:</strong> </p> <ol class="points"> <li>One primary advantage of using Dijkstra&apos;s Algorithm is that it has an almost linear time and space complexity.</li> <li>We can use this algorithm to calculate the shortest path from a single vertex to all other vertices and a single source vertex to a single destination vertex by stopping the algorithm once we get the shortest distance for the destination vertex.</li> <li>This algorithm only works for directed weighted graphs, and all the edges of this graph should be non-negative.</li> </ol> <p> <strong>Despite having multiple advantages, Dijkstra&apos;s algorithm has some disadvantages also, such as:</strong> </p> <ol class="points"> <li>Dijkstra&apos;s Algorithm performs a concealed exploration that utilizes a lot of time during the process.</li> <li>This algorithm is impotent to handle negative edges.</li> <li>Since this algorithm heads to the acyclic graph, it cannot calculate the exact shortest path.</li> <li>It also requires maintenance to keep a record of vertices that have been visited.</li> </ol> <h2>Some Applications of Dijkstra&apos;s Algorithm</h2> <p> <strong>Dijkstra&apos;s Algorithm has various real-world applications, some of which are stated below:</strong> </p> <ol class="points"> <tr><td>Digital Mapping Services in Google Maps:</td> There are various times when we have tried to find the distance in Google Maps either from our location to the nearest preferred location or from one city to another, which comprises multiple routes/paths connecting them; however, the application must display the minimum distance. This is only possible because Dijkstra&apos;s algorithm helps the application find the shortest between two given locations along the path. Let us consider the USA as a graph wherein the cities/places are represented as vertices, and the routes between two cities/places are represented as edges. Then with the help of Dijkstra&apos;s Algorithm, we can calculate the shortest routes between any two cities/places. </tr><tr><td>Social Networking Applications:</td> In many applications like Facebook, Twitter, Instagram, and more, many of us might have observed that these apps suggest the list of friends that a specific user may know. How do many social media companies implement this type of feature in an efficient and effective way, specifically when the system has over a billion users? The answer to this question is Dijkstra&apos;s Algorithm. The standard Dijkstra&apos;s Algorithm is generally used to estimate the shortest distance between the users measured through the connections or mutuality among them. When social networking is very small, it uses the standard Dijkstra&apos;s Algorithm in addition to some other features in order to determine the shortest paths. However, when the graph is much bigger, the standard algorithm takes several seconds to count, and thus, some advanced algorithms are used as the alternative. </tr><tr><td>Telephone Network:</td> As some of us might know, in a telephone network, each transmission line has a bandwidth, &apos;b&apos;. The bandwidth is the highest frequency that the transmission line can support. In general, if the frequency of the signal is higher in a specific line, the signal is reduced by that line. Bandwidth represents the amount of information that can be transmitted by the line. Let us consider a city a graph wherein the switching stations are represented using the vertices, the transmission lines are represented as the edges, and the bandwidth, &apos;b&apos;, is represented using the weight of the edges. Thus, as we can observe, the telephone network can also fall into the category of the shortest distance problem and can be solved using Dijkstra&apos;s Algorithm. </tr><tr><td>Flight Program:</td> Suppose that a person requires software to prepare an agenda of flights for customers. The agent has access to a database with all flights and airports. In addition to the flight number, origin airport, and destination, the flights also have departure and arrival times. So, in order to determine the earliest arrival time for the selected destination from the original airport and given start time, the agents make use of Dijkstra&apos;s Algorithm. </tr><tr><td>IP routing to find Open Shortest Path First:</td> Open Shortest Path First (abbreviated as OSPF) is a link-state routing protocol used to find the best path between the source and destination router with the help of its own Shortest Path First. Dijkstra&apos;s Algorithm is extensively utilized in the routing protocols required by the routers in order to update their forwarding table. The algorithm gives the shortest cost path from the source router to the other routers present in the network. </tr><tr><td>Robotic Path:</td> These days, drones and robots have come into existence, some operated manually and some automatically. The drones and robots which are operated automatically and used to deliver the packages to a given location or used for any certain task are configured with Dijkstra&apos;s Algorithm module so that whenever the source and destination are known, the drone and robot will move in the ordered direction by following the shortest path keeping the time taken to a minimum in order to deliver the packages. </tr><tr><td>Designate the File Server:</td> Dijkstra&apos;s Algorithm is also used to designate a file server in a Local Area Network (LAN). Suppose that an infinite period of time is needed for the transmission of the files from one computer to another. So, to minimize the number of &apos;hops&apos; from the file server to every other computer on the network, we will use Dijkstra&apos;s Algorithm. This algorithm will return the shortest path between the networks resulting in the minimum number of hops. </tr></ol> <h2>The Conclusion</h2> <ul> <li>In the above tutorial, firstly, we have understood the basic concepts of Graph along with its types and applications.</li> <li>We then learned about Dijkstra&apos;s Algorithm and its history.</li> <li>We have also understood the fundamental working of Dijkstra&apos;s Algorithm with the help of an example.</li> <li>After that, we studied how to write code for Dijkstra&apos;s Algorithm with the help of Pseudocode.</li> <li>We observed its implementation in programming languages like C, C++, Java, and Python with proper outputs and explanations.</li> <li>We have also understood the Time and Space Complexity of Dijkstra&apos;s Algorithm.</li> <li>Finally, we have discussed the advantages and disadvantages of Dijkstra&apos;s algorithm and some of its real-life applications.</li> </ul> <hr></nodes;>

توضيح:

في مقتطف التعليمات البرمجية أعلاه، قمنا بتعريف فئة عامة على أنها خوارزمية ديكسترا () . داخل هذه الفئة، قمنا بتعريف طريقة عامة بأنها خوارزمية ديكسترا () للعثور على أقصر مسافة من قمة المصدر إلى قمة الوجهة. داخل هذه الطريقة، قمنا بتعريف متغير لتخزين عدد العقد. قمنا بعد ذلك بتعريف مصفوفة منطقية لتخزين المعلومات المتعلقة بالقمم التي تمت زيارتها ومصفوفة أعداد صحيحة لتخزين المسافات الخاصة بها. في البداية، أعلنا القيم في كلا المصفوفتين كـ خطأ شنيع و قيمة الحد الأقصى ، على التوالى. لقد قمنا أيضًا بتعيين مسافة قمة المصدر على صفر واستخدمنا لحلقة لتحديث المسافة بين قمة المصدر وقمة الوجهة بأقل مسافة. قمنا بعد ذلك بتحديث مسافات القمم المجاورة للرأس المحدد عن طريق إجراء الاسترخاء وطباعة أقصر المسافات لكل قمة. لقد حددنا بعد ذلك طريقة للعثور على الحد الأدنى للمسافة من قمة المصدر إلى قمة الوجهة. قمنا بعد ذلك بتعريف الوظيفة الرئيسية حيث أعلنا عن رؤوس الرسم البياني وقمنا بإنشاء مثيل لها خوارزمية ديكسترا () فصل. وأخيرا، قمنا باستدعاء خوارزمية ديكسترا () طريقة للعثور على أقصر مسافة بين قمة المصدر وقمم الوجهة.

ونتيجة لذلك، تتم طباعة أقصر المسارات الممكنة المطلوبة لكل عقدة من العقدة المصدر للمستخدمين.

كود خوارزمية ديكسترا في بايثون

وفيما يلي تنفيذ خوارزمية ديكسترا في لغة البرمجة بايثون:

الملف: DikstraAlgorithm.py

 # Implementation of Dijkstra&apos;s Algorithm in Python # importing the sys module import sys # declaring the list of nodes for the graph nodes = [ [0, 0, 1, 0, 1, 0, 0], [0, 0, 1, 0, 0, 1, 0], [1, 1, 0, 1, 1, 0, 0], [1, 0, 1, 0, 0, 0, 1], [0, 0, 1, 0, 0, 1, 0], [0, 1, 0, 0, 1, 0, 1], [0, 0, 0, 1, 0, 1, 0] ] # declaring the list of edges for the graph edges = [ [0, 0, 1, 0, 2, 0, 0], [0, 0, 2, 0, 0, 3, 0], [1, 2, 0, 1, 3, 0, 0], [2, 0, 1, 0, 0, 0, 1], [0, 0, 3, 0, 0, 2, 0], [0, 3, 0, 0, 2, 0, 1], [0, 0, 0, 1, 0, 1, 0] ] # defining the function to find which node is to be visited next def toBeVisited(): global visitedAndDistance v = -10 for index in range(numberOfNodes): if visitedAndDistance[index][0] == 0 and (v <0 1 or visitedanddistance[index][1] <="visitedAndDistance[v][1]):" v="index" return # finding the number of nodes in graph numberofnodes="len(nodes[0])" visitedanddistance="[[0," 0]] for i range(numberofnodes - 1): visitedanddistance.append([0, sys.maxsize]) node range(numberofnodes): next to be visited tovisit="toBeVisited()" neighborindex updating new distances if nodes[tovisit][neighborindex]="=" and visitedanddistance[neighborindex][0]="=" 0: newdistance="visitedAndDistance[toVisit][1]" + edges[tovisit][neighborindex] visitedanddistance[neighborindex][1]> newDistance: visitedAndDistance[neighborIndex][1] = newDistance visitedAndDistance[toVisit][0] = 1 i = 0 # printing the distance for distance in visitedAndDistance: print(&apos;Distance of&apos;, chr(ord(&apos;A&apos;) + i), &apos;from source node:&apos;, distance[1]) i = i + 1 </0>

انتاج |

 Distance of A from source node: 0 Distance of B from source node: 3 Distance of C from source node: 1 Distance of D from source node: 2 Distance of E from source node: 2 Distance of F from source node: 4 Distance of G from source node: 3 

توضيح:

في مقتطف التعليمات البرمجية أعلاه، قمنا باستيراد ملف sys الوحدة النمطية وأعلنت القوائم التي تتكون من قيم العقد والحواف. لقد قمنا بعد ذلك بتعريف الوظيفة على أنها toBeVisited() للعثور على العقدة التي سيتم زيارتها بعد ذلك. ثم وجدنا العدد الإجمالي للعقد في الرسم البياني وقمنا بتعيين المسافات الأولية لكل عقدة. لقد قمنا بعد ذلك بحساب الحد الأدنى للمسافة من العقدة المصدر إلى العقدة الوجهة، وقمنا بإجراء الاسترخاء على العقد المجاورة، وقمنا بتحديث المسافات في القائمة. ثم قمنا بطباعة تلك المسافات من القائمة للمستخدمين.

ونتيجة لذلك، تتم طباعة أقصر المسارات الممكنة المطلوبة لكل عقدة من العقدة المصدر للمستخدمين.

تعقيد الزمان والمكان لخوارزمية ديكسترا

• التعقيد الزمني لخوارزمية ديكسترا O(سجل E V) حيث E هو عدد الحواف و V هو عدد القمم.
• التعقيد المكاني لخوارزمية ديكسترا هو O(V)، حيث V هو عدد القمم.

مزايا وعيوب خوارزمية ديكسترا

دعونا نناقش بعض مزايا خوارزمية ديكسترا:

1. إحدى المزايا الأساسية لاستخدام خوارزمية ديكسترا هي أنها تحتوي على تعقيد زمني ومكاني خطي تقريبًا.
2. يمكننا استخدام هذه الخوارزمية لحساب أقصر مسار من قمة واحدة إلى جميع القمم الأخرى ومن قمة مصدر واحدة إلى قمة وجهة واحدة عن طريق إيقاف الخوارزمية بمجرد حصولنا على أقصر مسافة لقمة الوجهة.
3. تعمل هذه الخوارزمية فقط مع الرسوم البيانية الموزونة الموجهة، ويجب أن تكون جميع حواف هذا الرسم البياني غير سلبية.

على الرغم من وجود العديد من المزايا، إلا أن خوارزمية ديكسترا لها بعض العيوب أيضًا، مثل:

1. تقوم خوارزمية Dijkstra بإجراء استكشاف مخفي يستهلك الكثير من الوقت أثناء العملية.
2. هذه الخوارزمية غير قادرة على التعامل مع الحواف السلبية.
3. نظرًا لأن هذه الخوارزمية تتجه إلى الرسم البياني غير الحلقي، فلا يمكنها حساب المسار الأقصر بالضبط.
4. يتطلب أيضًا الصيانة للاحتفاظ بسجل للقمم التي تمت زيارتها.

بعض تطبيقات خوارزمية ديكسترا

تحتوي خوارزمية ديكسترا على العديد من التطبيقات الواقعية، وبعضها مذكور أدناه:

خدمات الخرائط الرقمية في خرائط جوجل:هناك أوقات مختلفة حاولنا فيها العثور على المسافة في خرائط Google إما من موقعنا إلى أقرب موقع مفضل أو من مدينة إلى أخرى، والتي تشتمل على طرق/مسارات متعددة تربط بينها؛ ومع ذلك، يجب أن يعرض التطبيق الحد الأدنى للمسافة. هذا ممكن فقط لأن خوارزمية Dijkstra تساعد التطبيق في العثور على الأقصر بين موقعين محددين على طول المسار. دعونا ننظر إلى الولايات المتحدة الأمريكية كرسم بياني حيث يتم تمثيل المدن/الأماكن كرؤوس، ويتم تمثيل الطرق بين مدينتين/أماكن كحواف. ثم بمساعدة خوارزمية ديكسترا، يمكننا حساب أقصر الطرق بين أي مدينتين/مكانين.تطبيقات الشبكات الاجتماعية:في العديد من التطبيقات مثل فيسبوك وتويتر وإنستغرام وغيرها، ربما لاحظ الكثير منا أن هذه التطبيقات تقترح قائمة الأصدقاء التي قد يعرفها مستخدم معين. كيف تقوم العديد من شركات التواصل الاجتماعي بتنفيذ هذا النوع من الميزات بطريقة فعالة وفعالة، خاصة عندما يكون لدى النظام أكثر من مليار مستخدم؟ الجواب على هذا السؤال هو خوارزمية ديكسترا. تُستخدم خوارزمية Dijkstra القياسية بشكل عام لتقدير أقصر مسافة بين المستخدمين والتي يتم قياسها من خلال الاتصالات أو التبادلية فيما بينهم. عندما تكون شبكات التواصل الاجتماعي صغيرة جدًا، فإنها تستخدم خوارزمية ديكسترا القياسية بالإضافة إلى بعض الميزات الأخرى لتحديد أقصر المسارات. ومع ذلك، عندما يكون الرسم البياني أكبر بكثير، تستغرق الخوارزمية القياسية عدة ثوانٍ للعد، وبالتالي، يتم استخدام بعض الخوارزميات المتقدمة كبديل.شبكة الهاتف:كما قد يعلم البعض منا، في شبكة الهاتف، كل خط نقل لديه عرض النطاق الترددي، 'ب'. عرض النطاق الترددي هو أعلى تردد يمكن أن يدعمه خط النقل. وبشكل عام، إذا كان تردد الإشارة أعلى في خط معين، فإن الإشارة تنخفض بهذا الخط. يمثل عرض النطاق الترددي مقدار المعلومات التي يمكن إرسالها عبر الخط. دعونا نعتبر المدينة رسمًا بيانيًا يتم فيه تمثيل محطات التحويل باستخدام القمم، ويتم تمثيل خطوط النقل كحواف، ويتم تمثيل عرض النطاق الترددي 'b' باستخدام وزن الحواف. وبالتالي، كما يمكننا أن نلاحظ، يمكن أن تندرج شبكة الهاتف أيضًا ضمن فئة مشكلة أقصر مسافة ويمكن حلها باستخدام خوارزمية ديكسترا.برنامج الرحلة:لنفترض أن شخصًا ما يحتاج إلى برنامج لإعداد جدول رحلات الطيران للعملاء. الوكيل لديه حق الوصول إلى قاعدة بيانات لجميع الرحلات الجوية والمطارات. بالإضافة إلى رقم الرحلة والمطار الأصلي والوجهة، تحتوي الرحلات أيضًا على أوقات المغادرة والوصول. لذلك، من أجل تحديد أقرب وقت للوصول للوجهة المحددة من المطار الأصلي ووقت البدء المحدد، يستخدم الوكلاء خوارزمية Dijkstra.توجيه IP للعثور على فتح أقصر مسار أولاً:Open Shortest Path First (يُختصر بـ OSPF) هو بروتوكول توجيه حالة الارتباط يُستخدم للعثور على أفضل مسار بين جهاز التوجيه المصدر والوجهة بمساعدة أقصر مسار أولاً الخاص به. يتم استخدام خوارزمية Dijkstra على نطاق واسع في بروتوكولات التوجيه التي تتطلبها أجهزة التوجيه من أجل تحديث جدول إعادة التوجيه الخاص بها. توفر الخوارزمية أقصر مسار للتكلفة من جهاز التوجيه المصدر إلى أجهزة التوجيه الأخرى الموجودة في الشبكة.المسار الروبوتي:في هذه الأيام، ظهرت الطائرات بدون طيار والروبوتات إلى الوجود، بعضها يعمل يدويًا والبعض الآخر يعمل تلقائيًا. يتم تكوين الطائرات بدون طيار والروبوتات التي يتم تشغيلها تلقائيًا واستخدامها لتسليم الطرود إلى موقع معين أو استخدامها لأي مهمة معينة باستخدام وحدة خوارزمية Dijkstra بحيث تتحرك الطائرة بدون طيار والروبوت في الاتجاه المطلوب عندما يكون المصدر والوجهة معروفين. من خلال اتباع أقصر مسار مع تقليل الوقت المستغرق لتسليم الطرود إلى الحد الأدنى.تعيين خادم الملفات:تُستخدم خوارزمية Dijkstra أيضًا لتعيين خادم ملفات في شبكة المنطقة المحلية (LAN). لنفترض أن هناك حاجة إلى فترة زمنية لا نهائية لنقل الملفات من كمبيوتر إلى آخر. لذا، لتقليل عدد 'القفزات' من خادم الملفات إلى كل كمبيوتر آخر على الشبكة، سوف نستخدم خوارزمية ديكسترا. ستعيد هذه الخوارزمية أقصر مسار بين الشبكات مما يؤدي إلى الحد الأدنى من عدد القفزات.

الإستنتاج

• في البرنامج التعليمي أعلاه، أولاً، فهمنا المفاهيم الأساسية للرسم البياني بالإضافة إلى أنواعه وتطبيقاته.
• ثم تعرفنا على خوارزمية ديكسترا وتاريخها.
• لقد فهمنا أيضًا العمل الأساسي لخوارزمية ديكسترا بمساعدة مثال.
• بعد ذلك درسنا كيفية كتابة الكود لخوارزمية ديكسترا بمساعدة الكود الكاذب.
• وقد لاحظنا تنفيذه بلغات البرمجة مثل C وC++ وJava وPython مع المخرجات والشروحات المناسبة.
• لقد فهمنا أيضًا تعقيد الزمان والمكان لخوارزمية ديكسترا.
• أخيرًا، ناقشنا مزايا وعيوب خوارزمية ديكسترا وبعض تطبيقاتها الواقعية.