لماذا تستخدم خوارزمية Dijkstra إذا كان بإمكان البحث الأول عن البحث (BFS) نفس الشيء بشكل أسرع؟

Question

يمكن استخدام كلاهما للعثور على أقصر مسار من مصدر واحد. BFS يعمل في O(E+V), ، بينما يركض ديجكسترا O((V+E)*log(V)).

أيضًا ، رأيت Dijkstra يستخدم كثيرًا في بروتوكولات التوجيه.

وبالتالي ، لماذا تستخدم خوارزمية Dijkstra إذا كان بإمكان BFS فعل نفس الشيء بشكل أسرع؟

Answer 1

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

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

Answer 2

إذا كنت تفكر في مواقع السفر ، فهذه تستخدم خوارزمية Dijkstra بسبب الأوزان (المسافات) على العقد.

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

على سبيل المثال ، ضع في اعتبارك A -> (B, C) -> (F) مع أوزان الحافة التي قدمتها A->B = 10, A->C = 20, B->F = C->F = 5.

هنا ، إذا قمنا بتطبيق BFS ، فستكون الإجابة هي ABF أو ACF ، لأن كلاهما أقصر مسار (فيما يتعلق بعدد الحواف) ، ولكن إذا طبقنا DIJSTRA ، فإن الإجابة ستكون ABF فقط لأنها تعتبر الأوزان الموجودة على المتصلة طريق.

Answer 3

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

• مثل BFS للرسوم البيانية المرجح.
• إذا كانت جميع التكاليف متساوية ، فإن Dijkstra = BFS

مصدر : https://cs.stanford.edu/people/abisee/gs.pdf

Answer 4

من منظور التنفيذ ، يمكن تنفيذ خوارزمية Dijkstra تمامًا مثل BFS من خلال تبديل queue مع priority queue.

مصدر: أدخل الوصف الرابط هنا