مشكلة أقصر مسار

في نظرية المخططات ، تُعرف مشكلة أقصر مسار بأنها مشكلة إيجاد مسار بين رأسين (أو عقدتين) في مخطط بحيث يكون مجموع أوزان حوافه المكونة له في أدنى حد. ^{[ 1 ]}

يمكن نمذجة مشكلة إيجاد أقصر مسار بين تقاطعين على خريطة طريق كحالة خاصة من مشكلة أقصر مسار في الرسوم البيانية، حيث تمثل الرؤوس التقاطعات وتمثل الحواف أجزاء الطريق، ويتم ترجيح كل منها بطول أو مسافة كل جزء. ^{[ 2 ]}

تعريف

يمكن تعريف مسألة أقصر مسار للرسوم البيانية سواء كانت غير موجهة أو موجهة أو مختلطة . ينص تعريف الرسوم البيانية غير الموجهة على أنه يمكن اجتياز كل حافة في أي من الاتجاهين. أما الرسوم البيانية الموجهة فتتطلب أن تكون الرؤوس المتتالية متصلة بحافة موجهة مناسبة. ^{[ 3 ]}

يكون رأسان متجاورين عندما يكونان متصلين بحافة مشتركة. المسار في الرسم البياني غير الموجه هو سلسلة من الرؤوس. $P=(v_{1},v_{2},\ldots ,v_{n})\in V\times V\times \cdots \times V$ بحيث $v_{i}$ يقع بجوار $v_{i+1}$ ل $1\leq i<n$ مثل هذا المسار $P$ يُطلق عليه مسار طوله $n-1$ من $v_{1}$ ل $v_{n}$ . (ال $v_{i}$ هي متغيرات؛ يرتبط ترقيمها بموقعها في التسلسل ولا يشترط أن يرتبط بتسمية معيارية.) ^{[ 4 ]}

يترك $E=\{e_{i,j}\}$ أين $e_{i,j}$ هل الحافة تقع على كليهما؟ $v_{i}$ و $v_{j}$ . بالنظر إلى دالة وزن ذات قيم حقيقية $f:E\rightarrow \mathbb {R}$ ورسم بياني غير موجه (بسيط) $G$ أقصر طريق من $v$ ل $v'$ هو المسار $P=(v_{1},v_{2},\ldots ,v_{n})$ (أين $v_{1}=v$ و $v_{n}=v'$ ) ذلك على جميع الاحتمالات الممكنة $n$ يقلل المجموع $\sum _{i=1}^{n-1}f(e_{i,i+1}).$ عندما يكون لكل حافة في الرسم البياني وزن وحدة واحدة أو $f:E\rightarrow \{1\}$ وهذا يعادل إيجاد المسار ذي أقل عدد من الحواف.

وتسمى هذه المشكلة أحيانًا أيضًا مشكلة أقصر مسار لزوج واحد ، وذلك لتمييزها عن الاختلافات التالية: ^{[ 5 ]}

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

تتميز هذه التعميمات بخوارزميات أكثر كفاءة بشكل ملحوظ من النهج المبسط المتمثل في تشغيل خوارزمية أقصر مسار لزوج واحد على جميع أزواج الرؤوس ذات الصلة. ^{[ 6 ]}

الخوارزميات

توجد العديد من الخوارزميات المعروفة لحل هذه المشكلة ومتغيراتها.

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

يمكن العثور على خوارزميات إضافية وتقييمات مرتبطة بها في Cherkassky و Goldberg و Radzik (1996) .

أقصر المسارات من مصدر واحد

الرسوم البيانية غير الموجهة

الأوزان	تعقيد الخطة	مؤلف
$\mathbb {R}$ ₊	$O(V^{2})$	ديكسترا 1959
$\mathbb {R}$ ₊	$O((E+V)\log {V})$	جونسون 1977 ( كومة ثنائية )
$\mathbb {R}$ ₊	$O(E+V\log {V})$	فريدمان وتارجان 1984 ( كومة فيبوناتشي )
$\mathbb {N}$	$O(E)$	ثورب 1999 (يتطلب الضرب في زمن ثابت)
$\mathbb {R}$ ₊	$O(E{\sqrt {\log V\log \log V}})$	دوان وآخرون 2023

الرسوم البيانية غير الموزونة

الخوارزمية	تعقيد الخطة	مؤلف
البحث بالعرض أولاً	$O(E+V)$

الرسوم البيانية الموجهة غير الدورية

يمكن لخوارزمية تستخدم الفرز الطوبولوجي حل مشكلة أقصر مسار من مصدر واحد في وقت $Θ(E + V)$ في الرسوم البيانية الموجهة غير الدورية ذات الأوزان العشوائية. ^{[ 7 ]}

الرسوم البيانية الموجهة ذات الأوزان غير السالبة

الجدول التالي مأخوذ من Schrijver (2004) ، مع بعض التصحيحات والإضافات. تشير الخلفية الخضراء إلى أفضل حد تقاربي في الجدول؛ L هو أقصى طول (أو وزن) بين جميع الحواف، بافتراض أن أوزان الحواف أعداد صحيحة.

الأوزان	الخوارزمية	تعقيد الخطة	مؤلف
$\mathbb {R}$		$O(V^{2}EL)$	فورد 1956
$\mathbb {R}$	خوارزمية بيلمان-فورد	$O(VE)$	شيمبل 1955 ، بيلمان 1958 ، مور 1959
$\mathbb {R}$		$O(V^{2}\log {V})$	دانتزيج 1960
$\mathbb {R}$	خوارزمية ديكسترا مع القوائم	$O(V^{2})$	Leyzorek et al. 1957 ، Dijkstra 1959 ، Minty (انظر Pollack & Wiebenson 1960 )، Whiting & Hillier 1960
$\mathbb {R}$	خوارزمية ديكسترا مع الكومة الثنائية	$O((E+V)\log {V})$	جونسون 1977
$\mathbb {R}$	خوارزمية ديكسترا مع كومة فيبوناتشي	$O(E+V\log {V})$	فريدمان وتارجان 1984 ، فريدمان وتارجان 1987
$\mathbb {R}$	خوارزمية ديكسترا الكمومية مع قائمة التجاور	$O({\sqrt {VE}}\log ^{2}{V})$	دور وآخرون 2006 ^{[ 8 ]}
$\mathbb {R}$	نموذج ديكسترا - بلمان - فورد الهجين مع تقليل حدود البحث بتقسيم المشكلة إلى أجزاء أصغر	$O(E\log ^{2/3}{V})$	دوان وآخرون 2025 ^{[ 9 ]}
$\mathbb {N}$	خوارزمية ديال ^{[ 10 ]} ( خوارزمية ديكسترا باستخدام قائمة انتظار دلو مع L دلو)	$O(E+LV)$	اتصل بالرقم 1969
		$O(E\log {\log {L}})$	جونسون 1981 ، كارلسون وبوبليت 1983
	خوارزمية جابو	$O(E\log _{E/V}L)$	جابو 1983 ، جابو 1985
		$O(E+V{\sqrt {\log {L}}})$	أهوجا وآخرون 1990
$\mathbb {N}$	ثورب	$O(E+V\log {\log {V}})$	ثورب 2004

الرسوم البيانية الموجهة ذات الأوزان العشوائية بدون دورات سالبة

الأوزان	الخوارزمية	تعقيد الخطة	مؤلف
$\mathbb {R}$		$O(V^{2}EL)$	فورد 1956
$\mathbb {R}$	خوارزمية بيلمان-فورد	$O(VE)$	شيمبل 1955 ، بيلمان 1958 ، مور 1959
$\mathbb {R}$	خوارزمية جونسون-ديكسترا مع الكومة الثنائية	$O(VE+V\log V)$	جونسون 1977
$\mathbb {R}$	خوارزمية جونسون-ديكسترا مع كومة فيبوناتشي	$O(VE+V\log V)$	فريدمان وتارجان 1984 ، فريدمان وتارجان 1987 ، مقتبس بعد جونسون 1977
$\mathbb {Z}$	تم تطبيق تقنية جونسون على خوارزمية ديال ^{[ 10 ]}	$O(V(E+L))$	اتصل عام 1969 ، مقتبس عن جونسون عام 1977
$\mathbb {Z}$	طريقة النقطة الداخلية مع حل لابلاس	$O(E^{10/7}\log ^{O(1)}V\log ^{O(1)}L)$	كوهين وآخرون 2017
$\mathbb {Z}$	طريقة النقطة الداخلية مع $\ell _{p}$ محلل التدفق	$E^{4/3+o(1)}\log ^{O(1)}L$	أكسيوتيس، مادري وفلادو 2020
$\mathbb {Z}$	طريقة النقطة الداخلية القوية مع الرسم التخطيطي	$O((E+V^{3/2})\log ^{O(1)}V\log ^{O(1)}L)$	فان دن براند وآخرون، 2020
$\mathbb {Z}$	$\ell _{1}$ طريقة النقطة الداخلية مع بنية بيانات دورة النسبة الدنيا الديناميكية	$O(E^{1+o(1)}\log L)$	تشين وآخرون، 2022
$\mathbb {Z}$	استنادًا إلى التحلل ذي القطر المنخفض	$O(E\log ^{8}V\log L)$	بيرنشتاين، نانونغكاي وولف -نيلسن 2022
$\mathbb {R}$	أقصر المسارات المحدودة بالقفزات	$O(EV^{8/9}\log ^{O(1)}V)$	فينمان 2024
$\mathbb {R}$	أدوات شتاينر-تري	$O(V^{2+o(1)})$	خانا وسونغ 2026 ^{[ 11 ]}

الرسوم البيانية الموجهة ذات الأوزان العشوائية مع دورات سالبة

يجد دورة سالبة أو يحسب المسافات إلى جميع الرؤوس.

الأوزان	الخوارزمية	تعقيد الخطة	مؤلف
$\mathbb {Z}$		$O(E{\sqrt {V}}\log {N})$	أندرو ف. غولدبيرغ

الرسوم البيانية المستوية ذات الأوزان غير السالبة

الأوزان	الخوارزمية	تعقيد الخطة	مؤلف
$\mathbb {R} _{\geq 0}$		$O(V)$	هينزينجر وآخرون 1997

التطبيقات

تُعدّ تدفقات الشبكة ^{[ 12 ]} مفهومًا أساسيًا في نظرية الرسوم البيانية وبحوث العمليات، وتُستخدم غالبًا لنمذجة المشكلات المتعلقة بنقل البضائع أو السوائل أو المعلومات عبر الشبكة. تتضمن مشكلة تدفق الشبكة عادةً رسمًا بيانيًا موجهًا، حيث يُمثل كل ضلع أنبوبًا أو سلكًا أو طريقًا، ولكل ضلع سعة، وهي الحد الأقصى لكمية ما يمكن أن يتدفق عبره. والهدف هو إيجاد تدفق مُجدٍ يُعظّم التدفق من عقدة المصدر إلى عقدة المصب.

يمكن استخدام مسائل أقصر مسار لحل بعض مسائل تدفق الشبكة، لا سيما عند التعامل مع الشبكات ذات المصدر الواحد والمصب الواحد. في هذه الحالات، يمكننا تحويل مسألة تدفق الشبكة إلى سلسلة من مسائل أقصر مسار.

خطوات التحول

^{[ 13 ]}

إنشاء رسم بياني للبواقي:
- لكل حافة (u, v) في الرسم البياني الأصلي، قم بإنشاء حافتين في الرسم البياني المتبقي:
  - (u, v) بسعة c(u, v)
  - (v, u) بسعة 0
- يمثل الرسم البياني المتبقي السعة المتبقية المتاحة في الشبكة.
إيجاد أقصر مسار:
- استخدم خوارزمية أقصر مسار (مثل خوارزمية ديكسترا، خوارزمية بيلمان-فورد) لإيجاد أقصر مسار من عقدة المصدر إلى عقدة الوجهة في الرسم البياني المتبقي.
تعزيز التدفق:
- أوجد الحد الأدنى للسعة على طول أقصر مسار.
- قم بزيادة التدفق على حواف أقصر مسار بمقدار هذه السعة الدنيا.
- قلل سعة الحواف في الاتجاه الأمامي وزد سعة الحواف في الاتجاه الخلفي.
تحديث الرسم البياني للبواقي:
- قم بتحديث الرسم البياني المتبقي بناءً على التدفق المعزز.
يكرر:
- كرر الخطوات من 2 إلى 4 حتى لا يتم العثور على المزيد من المسارات من المصدر إلى المصب.

أقصر المسارات بين جميع الأزواج

تُعنى مسألة أقصر مسار بين جميع أزواج الرؤوس بإيجاد أقصر المسارات بين كل زوج من الرؤوس $v$ و $v'$ في الرسم البياني. وقد طرح شيمبل (1953) مسألة أقصر مسار بين جميع أزواج الرؤوس في الرسوم البيانية الموجهة غير الموزونة ، حيث لاحظ أنه يمكن حلها بعدد خطي من عمليات ضرب المصفوفات، ويستغرق ذلك زمنًا إجماليًا قدره $O (V/ 4)$ .

رسم بياني غير موجه

الأوزان	تعقيد الخطة	الخوارزمية
$\mathbb {R}$ ₊	$O(V^{3})$	خوارزمية فلويد-وارشال
$\{1,\infty \}$	$O(V^{\omega }\log V)$	خوارزمية سايدل (الوقت المتوقع للتشغيل باستخدام خوارزميات ضرب المصفوفات السريعة )
$\mathbb {N}$	$O(V^{3}/2^{\أوميغا (\log V)^{1/2}})$	ويليامز 2014
$\mathbb {R}$ ₊	$O(EV\log \alpha (E,V))$	بيتي وراماتشاندران 2002
$\mathbb {N}$	$O(EV)$	تم تطبيق طريقة Thorup 1999 على كل رأس (تتطلب عملية ضرب في وقت ثابت).

الرسم البياني الموجه

الأوزان	تعقيد الخطة	الخوارزمية
$\mathbb {R}$ (لا توجد دورات سلبية)	$O(V^{3})$	خوارزمية فلويد-وارشال
$\mathbb {N}$	$O(V^{3}/2^{\أوميغا (\log V)^{1/2}})$	ويليامز 2014
$\mathbb {R}$ (لا توجد دورات سلبية)	$O(V^{2.5}\log ^{2}{V})$	البحث الكمي ^{[ 14 ]}^{[ 15 ]}
$\mathbb {R}$ (لا توجد دورات سلبية)	$O(EV+V^{2}\log V)$	جونسون-ديكسترا
$\mathbb {R}$ (لا توجد دورات سلبية)	$O(EV+V^{2}\log \log V)$	بيتي 2004
$\mathbb {N}$	$O(EV+V^{2}\log \log V)$	هاجيروب 2000

التطبيقات

تُستخدم خوارزميات أقصر مسار لإيجاد الاتجاهات تلقائيًا بين المواقع الجغرافية، مثل توجيهات القيادة على مواقع الخرائط الإلكترونية مثل MapQuest أو خرائط جوجل . وتتوفر لهذا التطبيق خوارزميات متخصصة سريعة. ^{[ 16 ]}

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

في مجال الشبكات والاتصالات ، تُسمى مشكلة أقصر مسار أحيانًا بمشكلة المسار ذي أقل تأخير، وعادةً ما تُربط بمشكلة المسار الأوسع . على سبيل المثال، قد تبحث الخوارزمية عن أقصر مسار (أقل تأخير) وأوسع مسار، أو أوسع مسار (أقل تأخير). ^{[ 17 ]}

ومن التطبيقات الأكثر مرحاً ألعاب " ست درجات من الانفصال " التي تحاول إيجاد أقصر مسار في الرسوم البيانية مثل نجوم السينما الذين يظهرون في نفس الفيلم.

وتشمل التطبيقات الأخرى، التي غالباً ما يتم دراستها في بحوث العمليات ، تخطيط المصانع والمرافق، والروبوتات ، والنقل ، وتصميم الدوائر المتكاملة واسعة النطاق (VLSI) . ^{[ 18 ]}

شبكات الطرق

يمكن اعتبار شبكة الطرق بمثابة رسم بياني ذي أوزان موجبة. تمثل العقد تقاطعات الطرق، ويرتبط كل ضلع في الرسم البياني بجزء من الطريق بين تقاطعين. قد يتوافق وزن الضلع مع طول جزء الطريق المرتبط به، أو الوقت اللازم لاجتيازه، أو تكلفة اجتيازه. باستخدام الأضلاع الموجهة، يمكن أيضًا نمذجة الشوارع ذات الاتجاه الواحد. تتميز هذه الرسوم البيانية بأن بعض الأضلاع أكثر أهمية من غيرها للسفر لمسافات طويلة (مثل الطرق السريعة). وقد تم صياغة هذه الخاصية رسميًا باستخدام مفهوم بُعد الطريق السريع. ^{[ 19 ]} يوجد عدد كبير من الخوارزميات التي تستغل هذه الخاصية، وبالتالي فهي قادرة على حساب أقصر مسار بسرعة أكبر بكثير مما هو ممكن على الرسوم البيانية العامة.

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

تُعرف الخوارزمية الأسرع من حيث زمن الاستعلام باسم "تحديد المحاور"، وهي قادرة على حساب أقصر مسار على شبكات الطرق في أوروبا أو الولايات المتحدة في جزء من الميكروثانية. ^{[ 20 ]} ومن التقنيات الأخرى المستخدمة:

ALT ( بحث A* ، المعالم، وعدم مساواة المثلث )
أعلام القوس
التسلسلات الهرمية للانكماش
توجيه عقدة العبور
التقليم القائم على الوصول
وضع العلامات
ملصقات المحور

مشاكل ذات صلة

للحصول على معلومات حول مسائل أقصر مسار في الهندسة الحسابية ، انظر أقصر مسار إقليدي .

يمثل أقصر مسار متعدد غير متصل ^{[ 21 ]} تمثيلاً لشبكة المسار البدائية ضمن إطار نظرية الزحف . أما مسألة أوسع مسار فتسعى إلى إيجاد مسار يكون فيه الحد الأدنى لقيمة أي حافة أكبر ما يمكن.

يمكن تصنيف المشاكل الأخرى ذات الصلة إلى الفئات التالية.

مسارات ذات قيود

على عكس مسألة أقصر مسار، التي يمكن حلها في وقت متعدد الحدود في الرسوم البيانية الخالية من الدورات السالبة، تُسمى مسائل أقصر مسار التي تتضمن قيودًا إضافية على مسار الحل المطلوب " مسألة أقصر مسار مقيد أولًا" ، وهي أصعب في الحل. أحد الأمثلة على ذلك مسألة أقصر مسار مقيد ^{[ 22 ]} ، التي تسعى إلى تقليل التكلفة الإجمالية للمسار مع الحفاظ في الوقت نفسه على مقياس آخر أقل من عتبة معينة. هذا يجعل المسألة من فئة NP-كاملة (لا يُعتقد أن مثل هذه المسائل قابلة للحل بكفاءة لمجموعات البيانات الكبيرة، انظر مسألة P = NP ). مثال آخر من فئة NP-كاملة يتطلب تضمين مجموعة محددة من الرؤوس في المسار ^{[ 23 ]،} مما يجعل المسألة مشابهة لمسألة البائع المتجول (TSP). مسألة البائع المتجول هي مسألة إيجاد أقصر مسار يمر بكل رأس مرة واحدة فقط، ويعود إلى نقطة البداية. كما أن مسألة إيجاد أطول مسار في رسم بياني هي أيضًا من فئة NP-كاملة.

إمكانية الملاحظة الجزئية

تُعدّ مسألة المسافر الكندي ومسألة أقصر مسار عشوائي تعميماتٍ حيث لا يكون الرسم البياني معروفًا تمامًا للمتحرك، أو يتغير بمرور الوقت، أو حيث تكون الإجراءات (الاجتيازات) احتمالية. ^{[ 24 ]}^{[ 25 ]}

أقصر المسارات الاستراتيجية

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

الكشف عن الدورة السلبية

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

يمكن استخدام خوارزمية بيلمان -فورد للكشف عن دورة سلبية في الزمن $O(|V||E|)$ .
قام تشيركاسكي وغولدبرغ ^{[ 26 ]} باستعراض العديد من الخوارزميات الأخرى للكشف عن الدورات السلبية.

الإطار الجبري العام على أنصاف الحلقات: مسألة المسار الجبري

يمكن صياغة العديد من المسائل على شكل مسألة أقصر مسار، وذلك باستخدام مفاهيم مناسبة للجمع على طول مسار معين، ثم حساب القيمة الدنيا. ويتمثل النهج العام في اعتبار العمليتين بمثابة عمليتي نصف حلقة . يتم الضرب في نصف الحلقة على طول المسار، بينما يتم الجمع بين المسارات. يُعرف هذا الإطار العام بمسألة المسار الجبري. ^{[ 27 ]}^{[ 28 ]}^{[ 29 ]}

يمكن صياغة معظم خوارزميات أقصر مسار الكلاسيكية (والجديدة منها) على أنها حلول لأنظمة خطية على مثل هذه الهياكل الجبرية. ^{[ 30 ]}

وفي الآونة الأخيرة، تم تطوير إطار عمل أكثر عمومية لحل هذه المشكلات (ومشاكل أخرى أقل وضوحًا في ارتباطها) تحت شعار جبر التقييم . ^{[ 31 ]}

أقصر مسار في الشبكات العشوائية المعتمدة على الزمن

في الواقع، عادةً ما تكون شبكة النقل عشوائية وتعتمد على الزمن. وتعتمد مدة الرحلة على جزء من الطريق على عوامل عديدة، مثل حجم حركة المرور (مصفوفة الأصل والوجهة)، وأعمال الطرق، والطقس، والحوادث، وأعطال المركبات. ويُعدّ نموذج الشبكة العشوائية المعتمدة على الزمن (STD) نموذجًا أكثر واقعية لمثل هذه الشبكة. ^{[ 32 ]}^{[ 33 ]}

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

لمعالجة هذه المشكلة، يستخدم بعض الباحثين توزيع مدة الرحلة بدلاً من قيمتها المتوقعة. لذا، يجدون التوزيع الاحتمالي لإجمالي مدة الرحلة باستخدام طرق تحسين مختلفة، مثل البرمجة الديناميكية وخوارزمية ديكسترا . ^{[ 34 ]} تستخدم هذه الطرق التحسين العشوائي ، وتحديداً البرمجة الديناميكية العشوائية، لإيجاد أقصر مسار في الشبكات ذات أطوال الأقواس الاحتمالية. ^{[ 35 ]} يُستخدم مصطلحا " موثوقية وقت الرحلة" و "تباين وقت الرحلة" كمتضادين في أدبيات أبحاث النقل: فكلما زاد التباين، انخفضت موثوقية التنبؤات.

لمراعاة التباين، اقترح الباحثون تعريفين بديلين للمسار الأمثل في ظل عدم اليقين. المسار الأكثر موثوقية هو الذي يزيد من احتمالية الوصول في الوقت المحدد ضمن ميزانية زمنية محددة. أما المسار الموثوق به من الدرجة α فهو الذي يقلل من الميزانية الزمنية اللازمة للوصول في الوقت المحدد باحتمالية معينة.

أقصر مسار مقيد

مسألة أقصر مسار مقيد (RSP) هي شكل من أشكال مسألة أقصر مسار، حيث يوجد معياران للتحسين. لدينا رسم بياني موجه، لكل حافة فيه e تكلفة عددية غير سالبة c _e ، وتأخير عددي غير سالب d _e ، ورأسان محددان s و t، وميزانية تأخير عددية غير سالبة B. الهدف هو إيجاد مسار s-t بأقل تكلفة إجمالية، من بين المسارات التي لا يتجاوز تأخيرها الإجمالي B. تُصنف مسألة RSP ضمن المسائل الصعبة حسابيًا (NP-hard): وقد وردت في كتاب غاري وجونسون تحت مسمى المسألة ND30، "أقصر مسار مقيد الوزن". ولها خوارزمية تقريبية متعددة الحدود (FPTAS) منسوبة إلى هاسين ^{[ 36 ] ، والتي قام لورنز وراز}^[³⁷^] بتبسيطها وتحسينها لاحقًا.

توجد عدة تعميمات معروفة لهذه المشكلة:

في مسألة أقصر مسار مقيد بالموارد (RCSP) ، ^{[ 38 ]} يمكن لكل حافة أن تستهلك عدة موارد (بدلاً من الوقت فقط). لكل مورد r ميزانية مستقلة B _r . تستهلك كل حافة e مقدار d _e,r من كل مورد r . الهدف هو إيجاد مسار s--t بأقل تكلفة إجمالية، من بين المسارات التي تُحقق قيد الموارد لكل مورد.
في مسألة CSP المشتركة متعددة الأطراف ، ^{[ 39 ]} يمكن أن يكون هناك عدة أزواج من المصدر والهدف ( sj _، tj )، حيث j=1،2،.. هنا، الهدف هو إيجاد مسار لكل زوج _من المصدر والهدف، بأقل تكلفة إجمالية ، بشرط ألا يتجاوز إجمالي التأخير ميزانية التأخير.
تُعدّ مسألة تخصيص الموارد الجزئية (Fractional RSP) تبسيطًا لمسألة تخصيص الموارد (RSP) باستخدام البرمجة الخطية. وقد قدّمها هاندلر وزانغ ^{[ 40 ]} ، وقدّما خوارزمية توافقية لحلّها (في حالة مورد واحد). وأثبت ميلهورن وزيغلمان ^{[ 38 ]} أنه في حالة مورد واحد، تعمل الخوارزمية التوافقية في زمن متعدد الحدود، O(log( nCD ))، حيث n هو عدد العقد، والتكاليف أعداد صحيحة في النطاق من 0 إلى C ، والتأخيرات أعداد صحيحة في النطاق من 0 إلى D. أما في حالة وجود موارد متعددة، فيبقى زمن تشغيل الخوارزمية التوافقية غير محدد، ولكن يمكن حلّ البرمجة الخطية في زمن متعدد الحدود ضعيف باستخدام طريقة القطع الناقص.

انظر أيضاً

البحث ثنائي الاتجاه – خوارزمية تجد أقصر مسار بين رأسين في رسم بياني موجه
أقصر مسار إقليدي – مشكلة حساب أقصر المسارات حول العوائق الهندسية
شبكة التدفق – رسم بياني موجه حيث يكون للحواف سعة
توجيه أقصر K مسار – مشكلة حسابية في نظرية الرسم البياني
ضرب المصفوفات من النوع Min-plus – عملية رياضية على المصفوفات
البحث عن المسار – رسم المخططات بواسطة تطبيق حاسوبي
أقصر مسار للجسر
شجرة أقصر مسار - نوع من أنواع الأشجار الممتدة. صفحات تعرض أوصافًا مختصرة لأهداف إعادة التوجيه.
TRILL (الترابط الشفاف للعديد من الروابط)

مراجع

ملحوظات

^ أورتيجا أرانز، هيكتور. لانوس، دييغو ر.؛ جونزاليس إسكريبانو ، أرتورو (2015). مشكلة أقصر مسار . محاضرات تركيبية في علوم الكمبيوتر النظرية. شام: سبرينغر. دوى : 10.1007/978-3-031-02574-7 . رقم ISBN 978-3-031-01446-8.
↑ غوينين، برتراند (2014). مقدمة مبسطة في التحسين . يوشين كونيمان، ليفنت تونجيل ( الطبعة الأولى). ويست نياك: مطبعة جامعة كامبريدج. ص 27. ISBN 978-1-107-05344-1.
↑ ديو، نارسنج (17 أغسطس 2016). نظرية الرسوم البيانية مع تطبيقات في الهندسة وعلوم الحاسوب . منشورات كوريير دوفر. ISBN 978-0-486-80793-5.
↑ "المشي، والمسارات، والممرات، وركوب الدراجات، والدوائر" . نجاح الطلاب الأكاديمي . تم الاسترجاع في 13 يوليو 2026 .
↑ "شرح خوارزمية أقصر مسار مع مسائل" . GeeksforGeeks . 2023-11-02 . تم الاطلاع عليه بتاريخ 2026-07-13 .
↑ بروبيكر، بن (2025-08-06). "الطريقة الجديدة هي أسرع طريقة لإيجاد أفضل المسارات" . مجلة كوانتا . تم الاطلاع عليه بتاريخ 2026-07-13 .
^ كورمين وآخرون. 2001 ، ص. 655
↑ دور، كريستوف؛ هايليغمان، مارك؛ هوير، بيتر؛ محلة، مهدي (يناير 2006). "تعقيد الاستعلام الكمي لبعض مسائل الرسوم البيانية". مجلة SIAM للحوسبة . 35 (6): 1310-1328 . arXiv : quant-ph/0401091 . doi : 10.1137/050644719 . ISSN 0097-5397 . S2CID 14253494 .
↑ بروبيكر، بن (2025-08-06). "الطريقة الجديدة هي أسرع طريقة لإيجاد أفضل المسارات" . مجلة كوانتا . تم الاطلاع عليه بتاريخ 2025-08-11 .
1 2 ديال، روبرت ب. (1969). "الخوارزمية 360: غابة أقصر مسار مع الترتيب الطوبولوجي [ H ] " . اتصالات ACM . 12 (11): 632-633 . doi : 10.1145/363269.363610 . S2CID 6754003 .
↑ خانا، سانجيف؛ سونغ، جونكاي (18 فبراير 2026). "خوارزمية زمنية من الرتبة n ²⁺^o⁽¹⁾ لأقصر المسارات ذات الوزن السالب من مصدر واحد". arXiv : 2602.16638 [ cs.DS ].
↑ كورمن، توماس هـ. (31 يوليو 2009). مقدمة في الخوارزميات ( الطبعة الثالثة). مطبعة معهد ماساتشوستس للتكنولوجيا. ISBN 9780262533058.
^ كلاينبرج ، جون. تاردوس، إيفا (2005). تصميم الخوارزمية (الطبعة الأولى ). أديسون ويسلي. رقم ISBN 978-0321295354.
↑ دور، سي.؛ هوير، ب. (1996-07-18). "خوارزمية كمومية لإيجاد الحد الأدنى". arXiv : quant-ph/9607014 .
↑ نايبي، آران؛ ويليامز، في في (22-10-2014). "الخوارزميات الكمومية لمشاكل أقصر المسارات في الحالات المهيكلة". arXiv : 1410.6220 [ quant-ph ].
↑ ساندرز، بيتر (23 مارس 2009). "تخطيط المسار السريع" . نقاشات جوجل التقنية . مؤرشف من الأصل في 11 ديسمبر 2021.
↑ حسيني، س.؛ أ. ملوك؛ ي. أميرات (2005). "توجيه Q باستخدام أقصر المسارات K: خوارزمية توجيه جديدة لجودة الخدمة في شبكات الاتصالات" . الشبكات - المؤتمر الدولي للشبكات 2005، سلسلة محاضرات في علوم الحاسوب، المجلد 3421. المجلد 3421. سبرينغر، برلين، هايدلبرغ. الصفحات 164-172 . doi : 10.1007/978-3-540-31957-3_21 . ISBN 978-3-540-25338-9.
↑ تشين، داني ز. (ديسمبر 1996). "تطوير الخوارزميات والبرمجيات لمشاكل تخطيط المسار الهندسي". مجلة ACM Computing Surveys . 28 (4es). المقالة 18. doi : 10.1145/242224.242246 . S2CID 11761485 .
↑ أبراهام، إيتاي؛ فيات، آموس؛ غولدبيرغ، أندرو ف .؛ ويرنيك، ريناتو ف. "بعد الطريق السريع، وأقصر المسارات، والخوارزميات الفعالة بشكل مثبت" . ندوة ACM-SIAM حول الخوارزميات المنفصلة، الصفحات 782-793، 2010.
↑ أبراهام، إيتاي؛ ديلينغ، دانيال؛ غولدبيرغ، أندرو ف .؛ ويرنيك، ريناتو ف. research.microsoft.com/pubs/142356/HL-TR.pdf "خوارزمية تصنيف قائمة على المحاور لأقصر المسارات على شبكات الطرق" . ندوة حول الخوارزميات التجريبية، الصفحات 230-241، 2011.
↑ كروجر، مارتن (2005). "أقصر مسار متعدد غير متصل لتحليل التشابكات في الأنظمة البوليمرية ثنائية وثلاثية الأبعاد". مجلة اتصالات الفيزياء الحاسوبية . 168 (3): 209-232 . Bibcode : 2005CoPhC.168..209K . doi : 10.1016/j.cpc.2005.01.020 .
↑ لوزانو، ليوناردو؛ ميداليا، أندريس ل. (2013). "حول طريقة دقيقة لمسألة أقصر مسار مقيد". الحوسبة وبحوث العمليات . 40 (1): 378-384 . doi : 10.1016/j.cor.2012.07.008 .
↑ أوسانلو، كيفن؛ بورسوك، أندريه؛ غيتييه، كريستوف؛ كازيناف، تريستان؛ جاكوبين، إريك (2019). "الحل الأمثل لمسائل تخطيط المسار المقيد باستخدام الشبكات العصبية الالتفافية البيانية وبحث الشجرة الأمثل". المؤتمر الدولي IEEE/RSJ للروبوتات والأنظمة الذكية (IROS) لعام 2019. الصفحات 3519-3525 . arXiv : 2108.01036 . doi : 10.1109/IROS40897.2019.8968113 . ISBN 978-1-7281-4004-9. S2CID 210706773 .
↑ بار-نوي، أموتز؛ شيبر، باروخ (1991). "مسألة المسافر الكندي". وقائع الندوة السنوية الثانية لجمعية آلات الحوسبة والجمعية الصناعية للرياضيات التطبيقية حول الخوارزميات المنفصلة : 261-270 . CiteSeerX 10.1.1.1088.3015 .
↑ نيكولوفا، إيفدوكيا؛ كارغر، ديفيد ر. "تخطيط المسارات في ظل عدم اليقين: مشكلة المسافر الكندي" (ملف PDF) . وقائع المؤتمر الوطني الثالث والعشرين حول الذكاء الاصطناعي (AAAI) . الصفحات 969-974 . مؤرشف (ملف PDF) من الأصل بتاريخ 9 أكتوبر 2022.
↑ تشيركاسكي، بوريس ف.؛ غولدبيرغ، أندرو ف. (1999-06-01). "خوارزميات الكشف عن الدورات السلبية" . البرمجة الرياضية . 85 (2): 277-311 . doi : 10.1007/s101070050058 . ISSN 1436-4646 . S2CID 79739 .
^ زوج كلود (1967). "Sur des Algorithms pour des problèmes de cheminement dans les graphes Finis" [ حول خوارزميات مشاكل المسار في الرسوم البيانية المحدودة ] . في روزنتيهل، بيير (محرر). Théorie des graphes (journées Internationales d'études) [نظرية الرسوم البيانية (الندوة الدولية)] . روما (إيطاليا)، تموز/يوليه 1966. دونود (باريس)؛ جوردون وبريتش (نيويورك). ص. 271. أو سي إل سي 901424694 .
^ درنيام، جان كلود. زوج، كلود (1971). Problèmes de cheminement dans les graphes [ مشاكل المسار في الرسوم البيانية ] . دونود (باريس).
↑ باراس، جون؛ ثيودوراكوبولوس، جورج (4 أبريل 2010). مشاكل المسار في الشبكات . دار مورغان وكلايبول للنشر. ص 9–. ISBN 978-1-59829-924-3.
↑ غوندران، ميشيل؛ مينو، ميشيل (2008). "الفصل 4". الرسوم البيانية، والديودات، وشبه الحلقات: نماذج وخوارزميات جديدة . سبرينغر ساينس آند بيزنس ميديا. ISBN 978-0-387-75450-5.
↑ بولي، مارك؛ كولاس، يورغ (2011). "الفصل 6. جبر التقييم لمسائل المسار". الاستدلال العام: نظرية موحدة للاستدلال الآلي . جون وايلي وأولاده. ISBN 978-1-118-01086-0.
↑ لوي، آر بي، 1983. المسارات المثلى في الرسوم البيانية ذات الأوزان العشوائية أو متعددة الأبعاد. اتصالات رابطة آلات الحوسبة، 26(9)، ص 670-676.
↑ رجبي بهاء آبادي، مجتبى؛ شريعت محيماني، أفشين؛ بابائي، محسن؛ آهن، تشانغ ووك (2015). "إيجاد المسار متعدد الأهداف في شبكات الطرق العشوائية المعتمدة على الزمن باستخدام خوارزمية الفرز الجيني غير المهيمنة". أنظمة الخبراء مع التطبيقات . 42 (12): 5056-5064 . doi : 10.1016/j.eswa.2015.02.046 .
↑ أوليا، محمد حسام (2014). "إيجاد أقصر مسار في توزيع احتمالي مُدمج أسي-غاما لطول القوس". المجلة الدولية لبحوث العمليات . 21 (1) 64020: 25-37 . doi : 10.1504/IJOR.2014.064020 .
↑ أوليا، محمد حسام (2014). "تطبيق خوارزمية ديكسترا لحل مشكلة أقصر مسار عامة مع طول قوس ذي توزيع احتمالي طبيعي". المجلة الدولية لبحوث العمليات . 21 (2) 64541: 143-154 . doi : 10.1504/IJOR.2014.064541 .
↑ حسين، رفائيل (فبراير 1992). "مخططات تقريبية لمسألة أقصر مسار مقيد" . رياضيات بحوث العمليات . 17 (1): 36-42 . doi : 10.1287/moor.17.1.36 . ISSN 0364-765X .
↑ لورنز، دين هـ.؛ راز، داني (يونيو 2001). "مخطط تقريبي بسيط وفعال لمسألة أقصر مسار مقيد" . رسائل بحوث العمليات . 28 (5): 213-219 . doi : 10.1016/s0167-6377(01)00069-4 . ISSN 0167-6377 .
1 2 ميلهورن، كورت؛ زيغلمان، مارك (2000). "أقصر المسارات المقيدة بالموارد" . في باترسون، مايك س. (محرر). الخوارزميات - ESA 2000. سلسلة محاضرات في علوم الحاسوب. المجلد 1879. برلين، هايدلبرغ: سبرينغر. الصفحات 326-337 . doi : 10.1007/3-540-45253-2_30 . ISBN 978-3-540-45253-9.
↑ غارسيا-هيريديا، ديفيد؛ مولينا، إليسيندا؛ لاغونا، مانويل؛ ألونسو-أيوسو، أنطونيو (نوفمبر 2021). "طريقة حل لمسألة أقصر المسارات المتعددة ذات الموارد المشتركة المحدودة" . أنظمة الخبراء وتطبيقاتها . 182 115193. doi : 10.1016/j.eswa.2021.115193 . hdl : 10016/30793 . ISSN 0957-4174 .
↑ هاندلر، غابرييل ي.؛ زانغ، إسرائيل (ديسمبر 1980). "خوارزمية ثنائية لمسألة أقصر مسار مقيد" . الشبكات . 10 (4): 293-309 . doi : 10.1002/net.3230100403 . ISSN 0028-3045 .

فهرس

أهوجا، رافيندرا ك.؛ ميلهورن، كورت؛ أورلين، جيمس؛ تارجان، روبرت إي. (أبريل 1990). "خوارزميات أسرع لمسألة أقصر مسار" ( ملف PDF) . مجلة ACM . 37 (2). ACM: 213-223 . doi : 10.1145/77600.77615 . hdl : 1721.1/47994 . S2CID 5499589. مؤرشف (ملف PDF) من النسخة الأصلية بتاريخ 9 أكتوبر 2022.
أكسيوتيس، كيرياكوس؛ مادري، الكسندر. فلادو ، أدريان (2020). “التحكم في التداول من أجل الحد الأدنى من تدفق التكلفة بشكل أسرع في الرسوم البيانية لقدرة الوحدة”. في إيراني، ساندي (محرر). الندوة السنوية الحادية والستون لـ IEEE حول أسس علوم الكمبيوتر، FOCS 2020، دورهام، كارولاينا الشمالية، الولايات المتحدة الأمريكية، 16-19 نوفمبر 2020 . IEEE. ص 93 – 104. أرخايف : 2003.04863 . دوى : 10.1109/FOCS46700.2020.00018 . رقم ISBN 978-1-7281-9621-3.
بيلمان، ريتشارد (1958). "حول مسألة التوجيه" . مجلة الرياضيات التطبيقية الفصلية . 16 : 87-90 . doi : 10.1090/qam/102435 . MR 0102435 .
بيرنشتاين، آرون؛ نانونغكاي، دانوبون؛ وولف-نيلسن، كريستيان (2022). "أقصر المسارات أحادية المصدر ذات الوزن السالب في زمن شبه خطي". المؤتمر السنوي الثالث والستون لمؤسسة مهندسي الكهرباء والإلكترونيات (IEEE) حول أسس علوم الحاسوب (FOCS) لعام 2022. IEEE. الصفحات 600-611 . arXiv : 2203.03456 . doi : 10.1109/focs54457.2022.00063 . ISBN 978-1-6654-5519-0. S2CID 247958461 .
فان دن براند، جان؛ لي، ين تات؛ نانونغكاي، دانوبون؛ بينغ، ريتشارد؛ سارانوراك، ثاتشابول؛ سيدفورد، آرون؛ سونغ، تشاو؛ وانغ، دي (2020). "المطابقة الثنائية في وقت شبه خطي على الرسوم البيانية متوسطة الكثافة". في: إيراني، ساندي (محرر). المؤتمر السنوي الحادي والستون لمؤسسة مهندسي الكهرباء والإلكترونيات حول أسس علوم الحاسوب، FOCS 2020، دورهام، كارولاينا الشمالية، الولايات المتحدة الأمريكية، 16-19 نوفمبر 2020. IEEE. الصفحات 919-930 . arXiv : 2009.01802 . doi : 10.1109/FOCS46700.2020.00090 . ISBN 978-1-7281-9621-3.
تشين، لي؛ كينغ، راسموس؛ ليو، يانغ ب.؛ بينغ، ريتشارد؛ غوتنبرغ، ماكسيميليان بروبست؛ ساشديفا، سوشانت (2022). "التدفق الأقصى والتدفق الأدنى تكلفة في زمن شبه خطي". المؤتمر السنوي الثالث والستون لمؤسسة مهندسي الكهرباء والإلكترونيات حول أسس علوم الحاسوب، FOCS 2022، دنفر، كولورادو، الولايات المتحدة الأمريكية، 31 أكتوبر - 3 نوفمبر 2022. IEEE. الصفحات 612-623 . arXiv : 2203.00671 . doi : 10.1109/FOCS54457.2022.00064 . ISBN 978-1-6654-5519-0.
كوهين، مايكل ب.؛ مادري، ألكسندر؛ سانكوفسكي، بيوتر؛ فلادو، أدريان (2017). "أقصر المسارات ذات الوزن السالب وتدفق التكلفة الأدنى لوحدة السعة في ${\tilde {O}}(m^{10/7}\log W)$ "الوقت". في: كلاين، فيليب ن. (محرر). وقائع الندوة السنوية الثامنة والعشرين لجمعية ACM-SIAM حول الخوارزميات المنفصلة، SODA 2017، برشلونة، إسبانيا، فندق بورتا فيرا، 16-19 يناير . جمعية الرياضيات الصناعية والتطبيقية. الصفحات 752-771 . doi : 10.1137/1.9781611974782.48 .
دوان، ران؛ ماو، جيايي؛ شو، شينكاي؛ ين، لونغهوي (2023). "خوارزمية عشوائية لإيجاد أقصر مسار من مصدر واحد على الرسوم البيانية غير الموجهة ذات الأوزان الحقيقية". المؤتمر السنوي الرابع والستون لمؤسسة مهندسي الكهرباء والإلكترونيات (IEEE) حول أسس علوم الحاسوب (FOCS) لعام 2023. IEEE. الصفحات 484-492 . arXiv : 2307.04139 . doi : 10.1109/focs57990.2023.00035 . ISBN 979-8-3503-1894-4. S2CID 259501045 .
دوان، ران؛ ماو، جيايي؛ ماو، شياو؛ شو، شينكاي؛ ين، لونغهوي (2025). "تجاوز حاجز الفرز لأقصر المسارات الموجهة من مصدر واحد". وقائع الندوة السنوية السابعة والخمسين لجمعية آلات الحوسبة حول نظرية الحوسبة (STOC) . جمعية آلات الحوسبة. الصفحات 36-44 . doi : 10.1145/3717823.3718179 . ISBN 979-8-4007-1510-5.
تشيركاسكي، بوريس ف.؛ غولدبيرغ، أندرو ف .؛ رادزيك، توماش (1996). "خوارزميات أقصر المسارات: النظرية والتقييم التجريبي" . البرمجة الرياضية . السلسلة أ. 73 (2): 129-174 . doi : 10.1016/0025-5610(95)00021-6 . MR 1392160 .
كورمن، توماس هـ .؛ ليسرسون، تشارلز إي .؛ ريفست، رونالد ل .؛ شتاين، كليفورد (2001) [1990]. "أقصر المسارات من مصدر واحد وأقصر المسارات بين جميع الأزواج". مقدمة في الخوارزميات ( الطبعة الثانية). مطبعة معهد ماساتشوستس للتكنولوجيا وماكجرو هيل. الصفحات 580-642 . ISBN 0-262-03293-7.
دانتزيج، جي بي (يناير 1960). "حول أقصر طريق عبر الشبكة". علوم الإدارة . 6 (2): 187-190 . doi : 10.1287/mnsc.6.2.187 .
ديكسترا، إي دبليو (1959). "ملاحظة حول مسألتين تتعلقان بالرسوم البيانية". الرياضيات العددية . 1 : 269-271 . رمز Bibcode : 1959NuMat...1..269D . doi : 10.1007/BF01386390 . S2CID 123284777 .
فينمان، جيريمي ت. (2024). "أقصر المسارات من مصدر واحد بأوزان حقيقية سالبة في ${\tilde {O}}(mn^{8/9})$ "الوقت". في: موهار، بويان؛ شينكار، إيغور؛ أودونيل، رايان (محررون). وقائع الندوة السنوية السادسة والخمسين لجمعية آلات الحوسبة حول نظرية الحوسبة، STOC 2024، فانكوفر، كولومبيا البريطانية، كندا، 24-28 يونيو 2024. جمعية آلات الحوسبة. الصفحات 3-14 . arXiv : 2311.02520 . doi : 10.1145/3618260.3649614 .
فورد، إل آر (1956). نظرية تدفق الشبكة (تقرير). سانتا مونيكا، كاليفورنيا: مؤسسة راند. ص 923.
فريدمان، مايكل لورانس ؛ تارجان، روبرت إي. (1984). أكوام فيبوناتشي واستخداماتها في خوارزميات تحسين الشبكات المحسّنة . المؤتمر السنوي الخامس والعشرون لأسس علوم الحاسوب. معهد مهندسي الكهرباء والإلكترونيات . الصفحات 338-346 . doi : 10.1109/SFCS.1984.715934 . ISBN 0-8186-0591-X.
فريدمان، مايكل لورانس ؛ تارجان، روبرت إي. (1987). "أكوام فيبوناتشي واستخداماتها في خوارزميات تحسين الشبكات المحسّنة" . مجلة رابطة آلات الحوسبة . 34 (3): 596-615 . doi : 10.1145/28869.28874 . S2CID 7904683 .
جابو، إتش إن (1983). "خوارزميات التوسع لمشاكل الشبكات" (ملف PDF) . وقائع الندوة السنوية الرابعة والعشرين حول أسس علوم الحاسوب (FOCS 1983) . الصفحات 248-258 . doi : 10.1109/SFCS.1983.68 .
جابو، هارولد ن. (1985). "خوارزميات التوسع لمشاكل الشبكات" . مجلة علوم الحاسوب والنظم . 31 (2): 148-168 . doi : 10.1016/0022-0000(85)90039-X . MR 0828519 .
هاجيروب، توربن (2000). "تحسين أقصر المسارات على ذاكرة الوصول العشوائي للكلمات" . في: مونتاناري، أوجو؛ روليم، خوسيه دي بي؛ ويلزل، إيمو (محررون). وقائع الندوة الدولية السابعة والعشرين حول الأوتوماتا واللغات والبرمجة . الصفحات 61-72 . ISBN 978-3-540-67715-4.
هينزينجر، مونيكا ر.؛ كلاين، فيليب؛ راو، ساتيش؛ سوبرامانيان، سايرام (1997). "خوارزميات أسرع لإيجاد أقصر مسار للرسوم البيانية المستوية" . مجلة علوم الحاسوب والأنظمة . 55 (1): 3-23 . doi : 10.1006/jcss.1997.1493 .
جونسون، دونالد ب. (1977). "خوارزميات فعّالة لأقصر المسارات في الشبكات المتفرقة" . مجلة ACM . 24 (1): 1-12 . doi : 10.1145/321992.321993 . S2CID 207678246 .
جونسون، دونالد ب. (ديسمبر 1981). "طابور ذو أولوية تستغرق فيه عمليات التهيئة والترتيب وقتًا قدره $O (log log D)$ " . نظرية الأنظمة الرياضية . 15 (1): 295-309 . doi : 10.1007/BF01786986 . MR 0683047. S2CID 35703411 .
كارلسون، رولف ج.؛ بوبليت، باتريسيو ف. (1983). "خوارزمية من رتبة $O (m log log D)$ لأقصر المسارات" . الرياضيات التطبيقية المنفصلة . 6 (1): 91-93 . doi : 10.1016/0166-218X(83)90104-X . MR 0700028 .
ليزوريك، م.؛ غراي، ر.س.؛ جونسون، أ.أ.؛ لادو، و.س.؛ ميكر، س.ر. الابن؛ بيتري، ر.م.؛ سيتز، ر.ن. (1957). دراسة تقنيات النمذجة - التقرير السنوي الأول - 6 يونيو 1956 - 1 يوليو 1957 - دراسة لتقنيات النمذجة لأنظمة الاتصالات . كليفلاند، أوهايو: معهد كيس للتكنولوجيا.
مور، إي إف (1959). "أقصر مسار عبر متاهة". وقائع ندوة دولية حول نظرية التبديل (كامبريدج، ماساتشوستس، 2-5 أبريل 1957) . كامبريدج: مطبعة جامعة هارفارد. ص 285-292 .
بيتي، سيث؛ راماتشاندران، فيجايا (2002). "حساب أقصر المسارات باستخدام المقارنات والجمع" . وقائع الندوة السنوية الثالثة عشرة لجمعية ACM-SIAM حول الخوارزميات المنفصلة . الصفحات 267-276 . ISBN 978-0-89871-513-2.
بيتي، سيث (26 يناير 2004). "نهج جديد لإيجاد أقصر المسارات بين جميع الأزواج على الرسوم البيانية الموزونة الحقيقية" . علوم الحاسوب النظرية . 312 (1): 47-74 . doi : 10.1016/s0304-3975(03)00402-x .
بولاك، موريس؛ ويبنسون، والتر (مارس-أبريل 1960). "حل مسألة أقصر مسار - مراجعة". بحوث العمليات 8 ( 2): 224-230 . doi : 10.1287/opre.8.2.224 . ينسب خوارزمية ديكسترا إلى مينتي ("اتصال خاص") في الصفحة 225.
شريجفر، ألكسندر (2004). التحسين التوافقي - متعددات السطوح والكفاءة . الخوارزميات والتوافقية. المجلد 24. سبرينغر. المجلد أ، القسم 7.5ب، ص 103. ISBN 978-3-540-20456-5.
شيمبل، ألفونسو (1953). "المعايير الهيكلية لشبكات الاتصالات". نشرة الفيزياء الحيوية الرياضية . 15 (4): 501-507 . Bibcode : 1953BMaB...15..501S . doi : 10.1007/BF02476438 .
شيمبل، أ. (1955). "البنية في شبكات الاتصالات". وقائع ندوة شبكات المعلومات . نيويورك، نيويورك: مطبعة معهد بروكلين للفنون التطبيقية. ص 199-203 .
ثورب، ميكيل (1999). "أقصر المسارات غير الموجهة ذات المصدر الواحد بأوزان صحيحة موجبة في زمن خطي" . مجلة ACM . 46 (3): 362-394 . doi : 10.1145/316542.316548 . S2CID 207654795 .
ثورب، ميكيل (2004). "طوابير الأولوية الصحيحة ذات المفتاح المتناقص في وقت ثابت ومسألة أقصر المسارات من مصدر واحد" . مجلة علوم الحاسوب والنظم . 69 (3): 330-353 . doi : 10.1016/j.jcss.2004.04.003 .
وايتينغ، بي دي؛ هيلير، جيه إيه (مارس-يونيو 1960). "طريقة لإيجاد أقصر طريق عبر شبكة طرق". مجلة بحوث العمليات الفصلية . 11 (1/2): 37-40 . doi : 10.1057/jors.1960.32 .
ويليامز، رايان (2014). "مسارات أقصر لجميع الأزواج أسرع عبر تعقيد الدوائر". وقائع الندوة السنوية السادسة والأربعين لجمعية الحوسبة الآلية (ACM) حول نظرية الحوسبة (STOC '14) . نيويورك: ACM. الصفحات 664-673 . arXiv : 1312.6680 . doi : 10.1145/2591796.2591811 . MR 3238994 .

للمزيد من القراءة

ألتينتاش، جوكهان (2020). حلول دقيقة لمسائل أقصر مسار بناءً على تشبيهات ميكانيكية: في سياق المتاهات . أمازون ديجيتال سيرفيسز ذ.م.م. رقم ISBN 9798655831896.
فريجيوني، د.؛ ماركيتي-سباكاميلا، أ.؛ ناني، يو. (1998). "مسألة أقصر مسار من مصدر واحد ذي مخرجات محدودة ديناميكية بالكامل". وقائع الندوة السنوية السابعة لجمعية آلات الحوسبة وجمعية الرياضيات الصناعية والتطبيقية حول الخوارزميات المنفصلة . أتلانتا، جورجيا. الصفحات 212-221 . CiteSeerX 10.1.1.32.9856 .
دريفوس، إس إي (أكتوبر 1967). تقييم لبعض خوارزميات أقصر المسارات (ملف PDF) (تقرير). مشروع راند. القوات الجوية الأمريكية. RM-5433-PR. مؤرشف (ملف PDF) من الأصل في 17 نوفمبر 2015.DTIC AD-661265.

[1] أورتيجا أرانز، هيكتور. لانوس، دييغو ر.؛ جونزاليس إسكريبانو ، أرتورو (2015). مشكلة أقصر مسار . محاضرات تركيبية في علوم الكمبيوتر النظرية. شام: سبرينغر. دوى : 10.1007/978-3-031-02574-7 . رقم ISBN 978-3-031-01446-8.

[2] غوينين، برتراند (2014). مقدمة مبسطة في التحسين . يوشين كونيمان، ليفنت تونجيل ( الطبعة الأولى). ويست نياك: مطبعة جامعة كامبريدج. ص 27. ISBN 978-1-107-05344-1.

[3] ديو، نارسنج (17 أغسطس 2016). نظرية الرسوم البيانية مع تطبيقات في الهندسة وعلوم الحاسوب . منشورات كوريير دوفر. ISBN 978-0-486-80793-5.

[4] "المشي، والمسارات، والممرات، وركوب الدراجات، والدوائر" . نجاح الطلاب الأكاديمي . تم الاسترجاع في 13 يوليو 2026 .

[5] "شرح خوارزمية أقصر مسار مع مسائل" . GeeksforGeeks . 2023-11-02 . تم الاطلاع عليه بتاريخ 2026-07-13 .

[6] بروبيكر، بن (2025-08-06). "الطريقة الجديدة هي أسرع طريقة لإيجاد أفضل المسارات" . مجلة كوانتا . تم الاطلاع عليه بتاريخ 2026-07-13 .

[7] كورمين وآخرون. 2001 ، ص. 655

[8] دور، كريستوف؛ هايليغمان، مارك؛ هوير، بيتر؛ محلة، مهدي (يناير 2006). "تعقيد الاستعلام الكمي لبعض مسائل الرسوم البيانية". مجلة SIAM للحوسبة . 35 (6): 1310-1328 . arXiv : quant-ph/0401091 . doi : 10.1137/050644719 . ISSN 0097-5397 . S2CID 14253494 .

[9] بروبيكر، بن (2025-08-06). "الطريقة الجديدة هي أسرع طريقة لإيجاد أفضل المسارات" . مجلة كوانتا . تم الاطلاع عليه بتاريخ 2025-08-11 .

[dial69-10] 1 2 ديال، روبرت ب. (1969). "الخوارزمية 360: غابة أقصر مسار مع الترتيب الطوبولوجي [ H ] " . اتصالات ACM . 12 (11): 632-633 . doi : 10.1145/363269.363610 . S2CID 6754003 .

[11] خانا، سانجيف؛ سونغ، جونكاي (18 فبراير 2026). "خوارزمية زمنية من الرتبة n ²⁺^o⁽¹⁾ لأقصر المسارات ذات الوزن السالب من مصدر واحد". arXiv : 2602.16638 [ cs.DS ].

[12] كورمن، توماس هـ. (31 يوليو 2009). مقدمة في الخوارزميات ( الطبعة الثالثة). مطبعة معهد ماساتشوستس للتكنولوجيا. ISBN 9780262533058.

[13] كلاينبرج ، جون. تاردوس، إيفا (2005). تصميم الخوارزمية (الطبعة الأولى ). أديسون ويسلي. رقم ISBN 978-0321295354.

[14] دور، سي.؛ هوير، ب. (1996-07-18). "خوارزمية كمومية لإيجاد الحد الأدنى". arXiv : quant-ph/9607014 .

[15] نايبي، آران؛ ويليامز، في في (22-10-2014). "الخوارزميات الكمومية لمشاكل أقصر المسارات في الحالات المهيكلة". arXiv : 1410.6220 [ quant-ph ].

[16] ساندرز، بيتر (23 مارس 2009). "تخطيط المسار السريع" . نقاشات جوجل التقنية . مؤرشف من الأصل في 11 ديسمبر 2021.

[17] حسيني، س.؛ أ. ملوك؛ ي. أميرات (2005). "توجيه Q باستخدام أقصر المسارات K: خوارزمية توجيه جديدة لجودة الخدمة في شبكات الاتصالات" . الشبكات - المؤتمر الدولي للشبكات 2005، سلسلة محاضرات في علوم الحاسوب، المجلد 3421. المجلد 3421. سبرينغر، برلين، هايدلبرغ. الصفحات 164-172 . doi : 10.1007/978-3-540-31957-3_21 . ISBN 978-3-540-25338-9.

[18] تشين، داني ز. (ديسمبر 1996). "تطوير الخوارزميات والبرمجيات لمشاكل تخطيط المسار الهندسي". مجلة ACM Computing Surveys . 28 (4es). المقالة 18. doi : 10.1145/242224.242246 . S2CID 11761485 .

[19] أبراهام، إيتاي؛ فيات، آموس؛ غولدبيرغ، أندرو ف .؛ ويرنيك، ريناتو ف. "بعد الطريق السريع، وأقصر المسارات، والخوارزميات الفعالة بشكل مثبت" . ندوة ACM-SIAM حول الخوارزميات المنفصلة، الصفحات 782-793، 2010.

[20] أبراهام، إيتاي؛ ديلينغ، دانيال؛ غولدبيرغ، أندرو ف .؛ ويرنيك، ريناتو ف. research.microsoft.com/pubs/142356/HL-TR.pdf "خوارزمية تصنيف قائمة على المحاور لأقصر المسارات على شبكات الطرق" . ندوة حول الخوارزميات التجريبية، الصفحات 230-241، 2011.

[21] كروجر، مارتن (2005). "أقصر مسار متعدد غير متصل لتحليل التشابكات في الأنظمة البوليمرية ثنائية وثلاثية الأبعاد". مجلة اتصالات الفيزياء الحاسوبية . 168 (3): 209-232 . Bibcode : 2005CoPhC.168..209K . doi : 10.1016/j.cpc.2005.01.020 .

[22] لوزانو، ليوناردو؛ ميداليا، أندريس ل. (2013). "حول طريقة دقيقة لمسألة أقصر مسار مقيد". الحوسبة وبحوث العمليات . 40 (1): 378-384 . doi : 10.1016/j.cor.2012.07.008 .

[23] أوسانلو، كيفن؛ بورسوك، أندريه؛ غيتييه، كريستوف؛ كازيناف، تريستان؛ جاكوبين، إريك (2019). "الحل الأمثل لمسائل تخطيط المسار المقيد باستخدام الشبكات العصبية الالتفافية البيانية وبحث الشجرة الأمثل". المؤتمر الدولي IEEE/RSJ للروبوتات والأنظمة الذكية (IROS) لعام 2019. الصفحات 3519-3525 . arXiv : 2108.01036 . doi : 10.1109/IROS40897.2019.8968113 . ISBN 978-1-7281-4004-9. S2CID 210706773 .

[24] بار-نوي، أموتز؛ شيبر، باروخ (1991). "مسألة المسافر الكندي". وقائع الندوة السنوية الثانية لجمعية آلات الحوسبة والجمعية الصناعية للرياضيات التطبيقية حول الخوارزميات المنفصلة : 261-270 . CiteSeerX 10.1.1.1088.3015 .

[25] نيكولوفا، إيفدوكيا؛ كارغر، ديفيد ر. "تخطيط المسارات في ظل عدم اليقين: مشكلة المسافر الكندي" (ملف PDF) . وقائع المؤتمر الوطني الثالث والعشرين حول الذكاء الاصطناعي (AAAI) . الصفحات 969-974 . مؤرشف (ملف PDF) من الأصل بتاريخ 9 أكتوبر 2022.

[26] تشيركاسكي، بوريس ف.؛ غولدبيرغ، أندرو ف. (1999-06-01). "خوارزميات الكشف عن الدورات السلبية" . البرمجة الرياضية . 85 (2): 277-311 . doi : 10.1007/s101070050058 . ISSN 1436-4646 . S2CID 79739 .

[Pair1966-27] زوج كلود (1967). "Sur des Algorithms pour des problèmes de cheminement dans les graphes Finis" [ حول خوارزميات مشاكل المسار في الرسوم البيانية المحدودة ] . في روزنتيهل، بيير (محرر). Théorie des graphes (journées Internationales d'études) [نظرية الرسوم البيانية (الندوة الدولية)] . روما (إيطاليا)، تموز/يوليه 1966. دونود (باريس)؛ جوردون وبريتش (نيويورك). ص. 271. أو سي إل سي 901424694 .

[28] درنيام، جان كلود. زوج، كلود (1971). Problèmes de cheminement dans les graphes [ مشاكل المسار في الرسوم البيانية ] . دونود (باريس).

[BarasTheodorakopoulos2010-29] باراس، جون؛ ثيودوراكوبولوس، جورج (4 أبريل 2010). مشاكل المسار في الشبكات . دار مورغان وكلايبول للنشر. ص 9–. ISBN 978-1-59829-924-3.

[GondranMinoux2008-30] غوندران، ميشيل؛ مينو، ميشيل (2008). "الفصل 4". الرسوم البيانية، والديودات، وشبه الحلقات: نماذج وخوارزميات جديدة . سبرينغر ساينس آند بيزنس ميديا. ISBN 978-0-387-75450-5.

[PoulyKohlas2012-31] بولي، مارك؛ كولاس، يورغ (2011). "الفصل 6. جبر التقييم لمسائل المسار". الاستدلال العام: نظرية موحدة للاستدلال الآلي . جون وايلي وأولاده. ISBN 978-1-118-01086-0.

[32] لوي، آر بي، 1983. المسارات المثلى في الرسوم البيانية ذات الأوزان العشوائية أو متعددة الأبعاد. اتصالات رابطة آلات الحوسبة، 26(9)، ص 670-676.

[33] رجبي بهاء آبادي، مجتبى؛ شريعت محيماني، أفشين؛ بابائي، محسن؛ آهن، تشانغ ووك (2015). "إيجاد المسار متعدد الأهداف في شبكات الطرق العشوائية المعتمدة على الزمن باستخدام خوارزمية الفرز الجيني غير المهيمنة". أنظمة الخبراء مع التطبيقات . 42 (12): 5056-5064 . doi : 10.1016/j.eswa.2015.02.046 .

[34] أوليا، محمد حسام (2014). "إيجاد أقصر مسار في توزيع احتمالي مُدمج أسي-غاما لطول القوس". المجلة الدولية لبحوث العمليات . 21 (1) 64020: 25-37 . doi : 10.1504/IJOR.2014.064020 .

[35] أوليا، محمد حسام (2014). "تطبيق خوارزمية ديكسترا لحل مشكلة أقصر مسار عامة مع طول قوس ذي توزيع احتمالي طبيعي". المجلة الدولية لبحوث العمليات . 21 (2) 64541: 143-154 . doi : 10.1504/IJOR.2014.064541 .

[36] حسين، رفائيل (فبراير 1992). "مخططات تقريبية لمسألة أقصر مسار مقيد" . رياضيات بحوث العمليات . 17 (1): 36-42 . doi : 10.1287/moor.17.1.36 . ISSN 0364-765X .

[37] لورنز، دين هـ.؛ راز، داني (يونيو 2001). "مخطط تقريبي بسيط وفعال لمسألة أقصر مسار مقيد" . رسائل بحوث العمليات . 28 (5): 213-219 . doi : 10.1016/s0167-6377(01)00069-4 . ISSN 0167-6377 .

[:0-38] 1 2 ميلهورن، كورت؛ زيغلمان، مارك (2000). "أقصر المسارات المقيدة بالموارد" . في باترسون، مايك س. (محرر). الخوارزميات - ESA 2000. سلسلة محاضرات في علوم الحاسوب. المجلد 1879. برلين، هايدلبرغ: سبرينغر. الصفحات 326-337 . doi : 10.1007/3-540-45253-2_30 . ISBN 978-3-540-45253-9.

[39] غارسيا-هيريديا، ديفيد؛ مولينا، إليسيندا؛ لاغونا، مانويل؛ ألونسو-أيوسو، أنطونيو (نوفمبر 2021). "طريقة حل لمسألة أقصر المسارات المتعددة ذات الموارد المشتركة المحدودة" . أنظمة الخبراء وتطبيقاتها . 182 115193. doi : 10.1016/j.eswa.2021.115193 . hdl : 10016/30793 . ISSN 0957-4174 .

[40] هاندلر، غابرييل ي.؛ زانغ، إسرائيل (ديسمبر 1980). "خوارزمية ثنائية لمسألة أقصر مسار مقيد" . الشبكات . 10 (4): 293-309 . doi : 10.1002/net.3230100403 . ISSN 0028-3045 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]

[ 23 ]،

[ 24 ]

[ 25 ]

[ 26 ]

[ 27 ]

[ 28 ]

[ 29 ]

[ 30 ]

[ 31 ]

[ 32 ]

[ 33 ]

[ 34 ]

[ 35 ]

[ 36 ] ، والتي قام لورنز وراز

[

[ 39 ]

[ 40 ]

اللغة	العربية (RTL)
روابط موسوعية	30 رابطاً
المصدر الأصلي	ويكيبيديا ↗