Shortest Path Problem

Shortest Path Problem (SPP) هي مسألة إيجاد المسار ذي أصغر مجموع لأوزان الحواف بين عقدتين على رسم بياني موزون (موجَّه أو غير موجَّه)، بإحدى ثلاث صِيَغ رئيسة: single-source single-destination (نقطة-إلى-نقطة)، single-source all-destinations (مصدر واحد إلى كلّ الوجهات)، أو all-pairs (كلّ زوج). إنّها المسألة التأسيسية في OR على الرسوم البيانية؛ للحواف غير السالبة الحلّ المعياري هو الخوارزمية كثيرة الحدود التي عرّفها Dijkstra (1959) في ورقة من صفحتين في *Numerische Mathematik* (تنفيذ binary heap بـO((V+E)logV)). للحواف السالبة، يحلّ Bellman-Ford (Bellman 1958) بـO(VE) ويكشف الدورات السالبة. لـall-pairs، يحلّ Floyd-Warshall (Floyd 1962) بالبرمجة الديناميكية بـO(V³). Ahuja-Magnanti-Orlin (1993) *Network Flows* الكتاب المعياري. أكثر خوارزميات OR استدعاءً في الصناعة الحديثة — تعمل تحت خدمات الملاحة، الخرائط، بروتوكولات توجيه الحزم (OSPF)، ترتيب توصيل الطرود، تخطيط مسارات الطرق السريعة؛ على شبكات الطرق الوطنية، النُّهج الحديثة القائمة على المعالجة المسبقة (contraction hierarchies — Geisberger 2008) تقدّم زمن استعلام دون الميلّيثانية. TSP (#068) وVRP (#002) يستدعيان shortest path كروتين فرعي لكنّهما مسألتان مختلفتان: shortest path كثير الحدود، TSP/VRP صعبتان NP.