خوارزمية ديكسترا تعريف المسألة
حل سؤال خوارزمية ديكسترا تعريف المسألة.
بالعلم نسعى ونحصل على التميز وفي خدمة المتعلم نمضي قدما ولا نعرف التراجع فبالعلم يرتفع المتعلم إلى أعلى القمم ويحقق ارفع المراتب، لأن سلاح هذا الزمن هو العلم فمن تسلح به يكون قد حارب الجهل وساهم في تطوير مجتمعه وتقدمه فمن صار ماضيا في طلب العلم نال كل مراتب العلو والشرف وحقق أعلى الدرجات والتميز.
وننطلق بقوة حرصا على اقتناء الباحث وحصوله على المعلومة ذات البيانات السليمة الخالية من الأخطاء فنحن بصدد تلاشي ذلك.
السؤال :خوارزمية ديكسترا تعريف المسألة؟
الجواب هو :
لدينا بيان G (V,E) حيث انه بيان موزون ومترابط، أوزان وصلاته غير سالبة W E o mathbb R ^+ ، ولتكن s,t عقدتين ضمن هذا البيان.
نريد أن نجد مساراً بسيطاً يربط بين s و-t على أن يكون وزن هذا المسار (المُعرّف على أساس مجموع أوزان الوصلات التي يتألف منها) أصغر ما يمكن.
هذه هي المسألة بشكل عام ولكن الخوارزمية تحل مسألة أكثر عموميةً من هذه تتمثل في إيجاد أقصر مسار بين العقدة v وجميع العقد الأخرى.
الخوارزمية
سنطلق على العقدة التي نبدأ منها اسم العقدة الأولية. لتكن المسافة حتى العقدة Y هي المسافة من العقدة الأولية حتى العقدة Y. ستقوم خوارزمية دايكسترا بإسناد قيم معينة للمسافات وتحاول بعد ذلك القيام بتحسين هذه المسافات خطوة بعد خطوة.
أسند لكل عقدة قيمة ما تمثل المسافة دع هذه القيمة صفراً بالنسبة للعقدة الأولية، ولانهاية بالنسبة لباقي العقد.
علّم كافة العقد بأنها غير مزارة، علّم العقدة الأولية بأنها العقدة الحالية. اصنع مجموعة من العقد التي لم تتم زيارتها بعد وادعُ هذه المجموعة مجموعة العقد غير المزارة، تتضمن هذه المجموعة بدايةً كافة العقد.
قم بتحديد كافة جيران العقدة الحالية واحسب المسافات من هذه العقد إلى العقدة الحالية. قارن المسافات الجديدة مع المسافات القديمة واختر الأصغر. على سبيل المثال، لتكن العقدة الحالية A معلّمة بالمسافة 6، وليكن الضلع (الحافة) التي تصل A بالعقدة B بطول مقداره 2، وبالتالي فإن المسافة حتى العقدة B (من خلال العقدة A) ستكون 6+2 8. إذا كانت B معلمة سابقاً بمسافة أقل من 8 عندئذ لا نغير قيمة B، وإذا لم تكن كذلك فإننا نقوم بتغييرها.
عند الانتهاء من تعيين قيم كافة جيران العقدة الحالية، فإننا نعلم العقدة الحالية بأنها عقدة مزارة ونحذفها من مجموعة العقدة غير المزارة بحيث لا نقوم لاحقاً بإعادة زيارتها.
إذا تم تعليم العقدة الهدف بأنها عقدة مزارة (في حال البحث عن مسار بين عقدتين معطيتين) أو إذا كانت المسافة الأصغر من بين كافة العقد الموجودة في مجموعة العقد غير المزارة (في حال البحث عن جولة كاملة؛ يحدث ذلك في حال عدم وجود اتصال بين العقدة الأولية وباقي العقد غير المزارة) عندئذ يجب أن نتوقف وينتهي عمل الخوارزمية.
اختر العقدة غير المزارة التي لديها المسافة الأصغر وعلّم هذه العقدة بأنها العقدة الحالية وعُد إلى الخطوة 3.
الخوارزمية تعتمد بشكل كبير على انه اذا وجدنا المسار الاقصر بين v و-u لنُسمه p (t_0,t_1,...,t_k) بحيث ان k هو طول المسار ووزنه هو W(p) sum_ i 0 ^k W(t_i,t_ i+1 ) و- t_0 v , حينئذ اذا نظرنا للمسارات الجزئية من v حتى t_i نجد حينها انها هي الاقصر . وهذه المُعاينة تعتمد على أنَّ الأوزان موجبة .
ما يلي هو تطبيق الخوارزمية بلغة ++C , وهذا التطبيق هو ليس الأفضل بالضرورة ولكنه نموذج لطريقة التطبيق
Dijkstra
double[] dist new double[G.V()]
Edge[] pred new Edge[G.V()]
public Dijkstra(WeightedDigraph G, int s)
boolean[] marked new boolean[G.V()]
for (int v 0 v dist[v] + e.weight())
dist[w] dist[v] + e.weight()
pred[w] e
pq.insert(dist[w], w)
روابط خارجية
محاكاة لخوارزمية دكسترا
شريط بوابات معلوماتية خوارزميات
تصنيف كومنز Dijkstra's algorithm
تصنيف اختراعات هولندية
تصنيف استمثال توافقي
تصنيف خوارزميات
تصنيف خوارزميات بحث
تصنيف خوارزميات مخططات
تصنيف علم الحاسوب في 1959
صندوق معلومات خوارزمية
الصنف خوارزمية بحث
صورة Dijkstra Animation وسط محاكاة بسيطة لخوارزمية دكسترا
بنية المعطيات بيان
زمن أسوأ O( E + V log V )
خوارزمية ديكسترا إنج Dijkstra's algorithm هي خوارزمية تعنى بحل مسألة إيجاد المسار الأقصر بين عقدتين في بيان لا يحتوي على وصلات ذات أوزان سلبية. الخوارزمية مفيدة في عدة تطبيقات، مثل إيجاد الطريق الأقصر بين مدينتين ضمن خريطة، حيث قد تمثل أوزان الوصلات طول الشارع أو مستوى الازدحام في ذلك الشارع أو مجموعهما أو أي معيار مناسب آخر. واضع هذه الخوارزمية هو الهولندي ادسخر دغŒكسترا سنة 1959.