Chapitre III : Problème de plus court chemin – Théorie des graphes

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

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

يعرض الفصل خوارزميات حل مشكلة أقصر مسار حسب خصائص الرسم البياني، مثل خوارزمية ديكسترا عند وجود أوزان موجبة، وخوارزمية بيلمان في الرسوم بدون دورات، وخوارزمية بيلمان-فورد للرسوم العامة. كما يشير إلى خوارزميات المصفوفات مثل Floyd-Warshall وDantzig لحل مشكلة أقصر مسار بين جميع الأزواج.

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