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