خوارزمية دكسترا (بالإنجليزية: Dijkstra's algorithm) عبارة عن خوارزمية تهتم بحل مشكلة إيجاد المسار الأقصر بين رأسين في [[بيان (بنية بيانات)، مع أوزان إيجابية للوصلات، المسألة مهمة في مجموعة تطبيقات منها إيجاد الطريق الأقصر بين المدن في الخرائط في حين أن الأوزان قد تعني طول الشارع أو الزحمة في ذلك الشارع أو مجموعهما، واضع هذه الخوارزمية هو الهولندي ادسخر دیكسترا عام 1959.
تعريف المسألة
معطى مخطط G=(V,E) مع اوزان ايجابية على الأضلاع اي : W:E\to \mathbb{R}^+ ,وكذلك مُعطى رأسين : s,t .
نريد أن نجد مسار بسيط يربط بين s و-t بحيث أن طول المسار هو الأقصر.
هذه هي المسألة بشكل عام ولكن الخوارزمية تحل مسألة أعم من هذه بحيث انَّ المسألة التي يحلها هي بإعطائنا رأس v جد كل المسارات الخفيفة بين v وباقي الرؤوس .
الخوارزمية
الخوارزمية تعتمد بشكل كبير على انه اذا وجدنا المسار الاقصر بين 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 نجد حينها انها هي الاقصر . وهذه المُعاينة تعتمد على أنَّ الأوزان موجبة .
المراجع
areq.net
التصانيف
اختراعات هولندية استمثال توافقي خوارزميات خوارزميات بحث خوارزميات مخططات العلوم التطبيقية علم الحاسوب