Shortest path problem

In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized.^[1]

The problem of finding the shortest path between two intersections on a road map may be modeled as a special case of the shortest path problem in graphs, where the vertices correspond to intersections and the edges correspond to road segments, each weighted by the length or distance of each segment.^[2]

Definition

The shortest path problem can be defined for graphs whether undirected, directed, or mixed. The definition for undirected graphs states that every edge can be traversed in either direction. Directed graphs require that consecutive vertices be connected by an appropriate directed edge.^[3]

Two vertices are adjacent when they are both incident to a common edge. A path in an undirected graph is a sequence of vertices $P=(v_{1},v_{2},\ldots ,v_{n})\in V\times V\times \cdots \times V$ such that $v_{i}$ is adjacent to $v_{i+1}$ for $1\leq i<n$ . Such a path $P$ is called a path of length $n-1$ from $v_{1}$ to $v_{n}$ . (The $v_{i}$ are variables; their numbering relates to their position in the sequence and need not relate to a canonical labeling.)^[4]

Let $E=\{e_{i,j}\}$ where $e_{i,j}$ is the edge incident to both $v_{i}$ and $v_{j}$ . Given a real-valued weight function $f:E\rightarrow \mathbb {R}$ , and an undirected (simple) graph $G$ , the shortest path from $v$ to $v'$ is the path $P=(v_{1},v_{2},\ldots ,v_{n})$ (where $v_{1}=v$ and $v_{n}=v'$ ) that over all possible $n$ minimizes the sum $\sum _{i=1}^{n-1}f(e_{i,i+1}).$ When each edge in the graph has unit weight or $f:E\rightarrow \{1\}$ , this is equivalent to finding the path with fewest edges.

The problem is also sometimes called the single-pair shortest path problem, to distinguish it from the following variations:^[5]

The single-source shortest path problem, in which we have to find shortest paths from a source vertex v to all other vertices in the graph.
The single-destination shortest path problem, in which we have to find shortest paths from all vertices in the directed graph to a single destination vertex v. This can be reduced to the single-source shortest path problem by reversing the arcs in the directed graph.
مشكلة أقصر مسار بين جميع الأزواج ، والتي يتعين علينا فيها إيجاد أقصر المسارات بين كل زوج من الرؤوس 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

التطبيقات

Network flows^[12] are a fundamental concept in graph theory and operations research, often used to model problems involving the transportation of goods, liquids, or information through a network. A network flow problem typically involves a directed graph where each edge represents a pipe, wire, or road, and each edge has a capacity, which is the maximum amount that can flow through it. The goal is to find a feasible flow that maximizes the flow from a source node to a sink node.

Shortest Path Problems can be used to solve certain network flow problems, particularly when dealing with single-source, single-sink networks. In these scenarios, we can transform the network flow problem into a series of shortest path problems.

Transformation Steps

^[13]

Create a Residual Graph:
- For each edge (u, v) in the original graph, create two edges in the residual graph:
  - (u, v) with capacity c(u, v)
  - (v, u) with capacity 0
- The residual graph represents the remaining capacity available in the network.
Find the Shortest Path:
- Use a shortest path algorithm (e.g., Dijkstra's algorithm, Bellman-Ford algorithm) to find the shortest path from the source node to the sink node in the residual graph.
Augment the Flow:
- Find the minimum capacity along the shortest path.
- Increase the flow on the edges of the shortest path by this minimum capacity.
- Decrease the capacity of the edges in the forward direction and increase the capacity of the edges in the backward direction.
Update the Residual Graph:
- Update the residual graph based on the augmented flow.
Repeat:
- Repeat steps 2-4 until no more paths can be found from the source to the sink.

All-pairs shortest paths

The all-pairs shortest path problem finds the shortest paths between every pair of vertices $v$ , $v'$ in the graph. The all-pairs shortest paths problem for unweighted directed graphs was introduced by Shimbel (1953), who observed that it could be solved by a linear number of matrix multiplications that takes a total time of $O (V 4)$ .

Undirected graph

Weights	Time complexity	Algorithm
$\mathbb {R}$ ₊	$O(V^{3})$	Floyd–Warshall algorithm
$\{1,\infty \}$	$O(V^{\omega }\log V)$	Seidel's algorithm (expected running time using fast matrix multiplication algorithms)
$\mathbb {N}$	$O(V^{3}/2^{\Omega (\log V)^{1/2}})$	Williams 2014
$\mathbb {R}$ ₊	$O(EV\log \alpha (E,V))$	Pettie & Ramachandran 2002
$\mathbb {N}$	$O(EV)$	Thorup 1999 applied to every vertex (requires constant-time multiplication).

Directed graph

Weights	Time complexity	Algorithm
$\mathbb {R}$ (no negative cycles)	$O(V^{3})$	Floyd–Warshall algorithm
$\mathbb {N}$	$O(V^{3}/2^{\Omega (\log V)^{1/2}})$	Williams 2014
$\mathbb {R}$ (no negative cycles)	$O(V^{2.5}\log ^{2}{V})$	Quantum search^[14]^[15]
$\mathbb {R}$ (no negative cycles)	$O(EV+V^{2}\log V)$	Johnson–Dijkstra
$\mathbb {R}$ (no negative cycles)	$O(EV+V^{2}\log \log V)$	Pettie 2004
$\mathbb {N}$	$O(EV+V^{2}\log \log V)$	Hagerup 2000

Applications

تُستخدم خوارزميات أقصر مسار لإيجاد الاتجاهات تلقائيًا بين المواقع الجغرافية، مثل توجيهات القيادة على مواقع الخرائط الإلكترونية مثل 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 2Dial, Robert B. (1969). "Algorithm 360: Shortest-Path Forest with Topological Ordering [H]". Communications of the ACM. 12 (11): 632–633. doi:10.1145/363269.363610. S2CID 6754003.
↑Khanna, Sanjeev; Song, Junkai (February 18, 2026). "An n^2+o(1) Time Algorithm for Single-Source Negative Weight Shortest Paths". arXiv:2602.16638 [cs.DS].
↑Cormen, Thomas H. (July 31, 2009). Introduction to Algorithms (3rd ed.). MIT Press. ISBN 9780262533058.
↑Kleinberg, Jon; Tardos, Éva (2005). Algorithm Design (1st ed.). Addison-Wesley. ISBN 978-0321295354.
↑Dürr, C.; Høyer, P. (1996-07-18). "A Quantum Algorithm for Finding the Minimum". arXiv:quant-ph/9607014.
↑Nayebi, Aran; Williams, V. V. (2014-10-22). "Quantum algorithms for shortest paths problems in structured instances". arXiv:1410.6220 [quant-ph].
↑Sanders, Peter (March 23, 2009). "Fast route planning". Google Tech Talk. Archived from the original on 2021-12-11.
↑Hoceini, S.; A. Mellouk; Y. Amirat (2005). "K-Shortest Paths Q-Routing: A New QoS Routing Algorithm in Telecommunication Networks". Networking - ICN 2005, Lecture Notes in Computer Science, Vol. 3421. Vol. 3421. Springer, Berlin, Heidelberg. pp. 164–172. doi:10.1007/978-3-540-31957-3_21. ISBN 978-3-540-25338-9.
↑Chen, Danny Z. (December 1996). "Developing algorithms and software for geometric path planning problems". ACM Computing Surveys. 28 (4es). Article 18. doi:10.1145/242224.242246. S2CID 11761485.
↑Abraham, Ittai; Fiat, Amos; Goldberg, Andrew V.; Werneck, Renato F. "Highway Dimension, Shortest Paths, and Provably Efficient Algorithms". ACM-SIAM Symposium on Discrete Algorithms, pages 782–793, 2010.
↑Abraham, Ittai; Delling, Daniel; Goldberg, Andrew V.; Werneck, Renato F. research.microsoft.com/pubs/142356/HL-TR.pdf "A Hub-Based Labeling Algorithm for Shortest Paths on Road Networks". Symposium on Experimental Algorithms, pages 230–241, 2011.
↑Kroger, Martin (2005). "Shortest multiple disconnected path for the analysis of entanglements in two- and three-dimensional polymeric systems". Computer Physics Communications. 168 (3): 209–232. Bibcode:2005CoPhC.168..209K. doi:10.1016/j.cpc.2005.01.020.
↑Lozano, Leonardo; Medaglia, Andrés L (2013). "On an exact method for the constrained shortest path problem". Computers & Operations Research. 40 (1): 378–384. doi:10.1016/j.cor.2012.07.008.
↑Osanlou, Kevin; Bursuc, Andrei; Guettier, Christophe; Cazenave, Tristan; Jacopin, Eric (2019). "Optimal Solving of Constrained Path-Planning Problems with Graph Convolutional Networks and Optimized Tree Search". 2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). pp. 3519–3525. arXiv:2108.01036. doi:10.1109/IROS40897.2019.8968113. ISBN 978-1-7281-4004-9. S2CID 210706773.
↑Bar-Noy, Amotz; Schieber, Baruch (1991). "The canadian traveller problem". Proceedings of the Second Annual ACM-SIAM Symposium on Discrete Algorithms: 261–270. CiteSeerX 10.1.1.1088.3015.
↑Nikolova, Evdokia; Karger, David R. "Route planning under uncertainty: the Canadian traveller problem"(PDF). Proceedings of the 23rd National Conference on Artificial Intelligence (AAAI). pp. 969–974. Archived(PDF) from the original on 2022-10-09.
↑Cherkassky, Boris V.; Goldberg, Andrew V. (1999-06-01). "Negative-cycle detection algorithms". Mathematical Programming. 85 (2): 277–311. doi:10.1007/s101070050058. ISSN 1436-4646. S2CID 79739.
↑Pair, Claude (1967). "Sur des algorithmes pour des problèmes de cheminement dans les graphes finis" [On algorithms for path problems in finite graphs]. In Rosentiehl, Pierre (ed.). Théorie des graphes (journées internationales d'études) [Theory of Graphs (international symposium)]. Rome (Italy), July 1966. Dunod (Paris); Gordon and Breach (New York). p. 271. OCLC 901424694.
↑Derniame, Jean Claude; Pair, Claude (1971). Problèmes de cheminement dans les graphes[Path Problems in Graphs]. Dunod (Paris).
↑Baras, John; Theodorakopoulos, George (4 April 2010). Path Problems in Networks. Morgan & Claypool Publishers. pp. 9–. ISBN 978-1-59829-924-3.
↑Gondran, Michel; Minoux, Michel (2008). "chapter 4". Graphs, Dioids and Semirings: New Models and Algorithms. Springer Science & Business Media. ISBN 978-0-387-75450-5.
↑Pouly, Marc; Kohlas, Jürg (2011). "Chapter 6. Valuation Algebras for Path Problems". Generic Inference: A Unifying Theory for Automated Reasoning. John Wiley & Sons. ISBN 978-1-118-01086-0.
↑Loui, R.P., 1983. Optimal paths in graphs with stochastic or multidimensional weights. Communications of the ACM, 26(9), pp.670-676.
↑Rajabi-Bahaabadi, Mojtaba; Shariat-Mohaymany, Afshin; Babaei, Mohsen; Ahn, Chang Wook (2015). "Multi-objective path finding in stochastic time-dependent road networks using non-dominated sorting genetic algorithm". Expert Systems with Applications. 42 (12): 5056–5064. doi:10.1016/j.eswa.2015.02.046.
↑Olya, Mohammad Hessam (2014). "Finding shortest path in a combined exponential – gamma probability distribution arc length". International Journal of Operational Research. 21 (1) 64020: 25–37. doi:10.1504/IJOR.2014.064020.
↑Olya, Mohammad Hessam (2014). "Applying Dijkstra's algorithm for general shortest path problem with normal probability distribution arc length". International Journal of Operational Research. 21 (2) 64541: 143–154. doi:10.1504/IJOR.2014.064541.
↑Hassin, Refael (February 1992). "Approximation Schemes for the Restricted Shortest Path Problem". Mathematics of Operations Research. 17 (1): 36–42. doi:10.1287/moor.17.1.36. ISSN 0364-765X.
↑Lorenz, Dean H.; Raz, Danny (June 2001). "A simple efficient approximation scheme for the restricted shortest path problem". Operations Research Letters. 28 (5): 213–219. doi:10.1016/s0167-6377(01)00069-4. ISSN 0167-6377.
12Mehlhorn, Kurt; Ziegelmann, Mark (2000). "Resource Constrained Shortest Paths". In Paterson, Mike S. (ed.). Algorithms - ESA 2000. Lecture Notes in Computer Science. Vol. 1879. Berlin, Heidelberg: Springer. pp. 326–337. doi:10.1007/3-540-45253-2_30. ISBN 978-3-540-45253-9.
↑García-Heredia, David; Molina, Elisenda; Laguna, Manuel; Alonso-Ayuso, Antonio (November 2021). "A solution method for the shared resource-constrained multi-shortest path problem". Expert Systems with Applications. 182 115193. doi:10.1016/j.eswa.2021.115193. hdl:10016/30793. ISSN 0957-4174.
↑Handler, Gabriel Y.; Zang, Israel (December 1980). "A dual algorithm for the constrained shortest path problem". Networks. 10 (4): 293–309. doi:10.1002/net.3230100403. ISSN 0028-3045.

Bibliography

Ahuja, Ravindra K.; Mehlhorn, Kurt; Orlin, James; Tarjan, Robert E. (April 1990). "Faster algorithms for the shortest path problem"(PDF). Journal of the ACM. 37 (2). ACM: 213–223. doi:10.1145/77600.77615. hdl:1721.1/47994. S2CID 5499589. Archived(PDF) from the original on 2022-10-09.
Axiotis, Kyriakos; Mądry, Aleksander; Vladu, Adrian (2020). "Circulation control for faster minimum cost flow in unit-capacity graphs". In Irani, Sandy (ed.). 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16–19, 2020. IEEE. pp. 93–104. arXiv:2003.04863. doi:10.1109/FOCS46700.2020.00018. ISBN 978-1-7281-9621-3.
Bellman, Richard (1958). "On a routing problem". Quarterly of Applied Mathematics. 16: 87–90. doi:10.1090/qam/102435. MR 0102435.
Bernstein, Aaron; Nanongkai, Danupon; Wulff-Nilsen, Christian (2022). "Negative-Weight Single-Source Shortest Paths in Near-linear Time". 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS). IEEE. pp. 600–611. arXiv:2203.03456. doi:10.1109/focs54457.2022.00063. ISBN 978-1-6654-5519-0. S2CID 247958461.
van den Brand, Jan; Lee, Yin Tat; Nanongkai, Danupon; Peng, Richard; Saranurak, Thatchaphol; Sidford, Aaron; Song, Zhao; Wang, Di (2020). "Bipartite matching in nearly-linear time on moderately dense graphs". In Irani, Sandy (ed.). 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16–19, 2020. IEEE. pp. 919–930. arXiv:2009.01802. doi:10.1109/FOCS46700.2020.00090. ISBN 978-1-7281-9621-3.
Chen, Li; Kyng, Rasmus; Liu, Yang P.; Peng, Richard; Gutenberg, Maximilian Probst; Sachdeva, Sushant (2022). "Maximum flow and minimum-cost flow in almost-linear time". 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 – November 3, 2022. IEEE. pp. 612–623. arXiv:2203.00671. doi:10.1109/FOCS54457.2022.00064. ISBN 978-1-6654-5519-0.
Cohen, Michael B.; Mądry, Aleksander; Sankowski, Piotr; Vladu, Adrian (2017). "Negative-weight shortest paths and unit capacity minimum cost flow in ${\tilde {O}}(m^{10/7}\log W)$ time". In Klein, Philip N. (ed.). Proceedings of the Twenty-Eighth Annual ACM–SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16–19. Society for Industrial and Applied Mathematics. pp. 752–771. doi:10.1137/1.9781611974782.48.
Duan, Ran; Mao, Jiayi; Shu, Xinkai; Yin, Longhui (2023). "A Randomized Algorithm for Single-Source Shortest Path on Undirected Real-Weighted Graphs". 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS). IEEE. pp. 484–492. arXiv:2307.04139. doi:10.1109/focs57990.2023.00035. ISBN 979-8-3503-1894-4. S2CID 259501045.
Duan, Ran; Mao, Jiayi; Mao, Xiao; Shu, Xinkai; Yin, Longhui (2025). "Breaking the Sorting Barrier for Directed Single-Source Shortest Paths". Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC). Association for Computing Machinery. pp. 36–44. doi:10.1145/3717823.3718179. ISBN 979-8-4007-1510-5.
Cherkassky, Boris V.; Goldberg, Andrew V.; Radzik, Tomasz (1996). "Shortest paths algorithms: theory and experimental evaluation". Mathematical Programming. Ser. A. 73 (2): 129–174. doi:10.1016/0025-5610(95)00021-6. MR 1392160.
Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. "Single-Source Shortest Paths and All-Pairs Shortest Paths". Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. 580–642. ISBN 0-262-03293-7.
Dantzig, G. B. (January 1960). "On the Shortest Route through a Network". Management Science. 6 (2): 187–190. doi:10.1287/mnsc.6.2.187.
Dijkstra, E. W. (1959). "A note on two problems in connexion with graphs". Numerische Mathematik. 1: 269–271. Bibcode:1959NuMat...1..269D. doi:10.1007/BF01386390. S2CID 123284777.
Fineman, Jeremy T. (2024). "Single-source shortest paths with negative real weights in ${\tilde {O}}(mn^{8/9})$ time". In Mohar, Bojan; Shinkar, Igor; O'Donnell, Ryan (eds.). Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24–28, 2024. Association for Computing Machinery. pp. 3–14. arXiv:2311.02520. doi:10.1145/3618260.3649614.
Ford, L. R. (1956). Network Flow Theory (Report). Santa Monica, CA: RAND Corporation. P-923.
Fredman, Michael Lawrence; Tarjan, Robert E. (1984). Fibonacci heaps and their uses in improved network optimization algorithms. 25th Annual Symposium on Foundations of Computer Science. IEEE. pp. 338–346. doi:10.1109/SFCS.1984.715934. ISBN 0-8186-0591-X.
Fredman, Michael Lawrence; Tarjan, Robert E. (1987). "Fibonacci heaps and their uses in improved network optimization algorithms". Journal of the Association for Computing Machinery. 34 (3): 596–615. doi:10.1145/28869.28874. S2CID 7904683.
Gabow, H. N. (1983). "Scaling algorithms for network problems"(PDF). Proceedings of the 24th Annual Symposium on Foundations of Computer Science (FOCS 1983). pp. 248–258. doi:10.1109/SFCS.1983.68.
Gabow, Harold N. (1985). "Scaling algorithms for network problems". Journal of Computer and System Sciences. 31 (2): 148–168. doi:10.1016/0022-0000(85)90039-X. MR 0828519.
Hagerup, Torben (2000). "Improved Shortest Paths on the Word RAM". In Montanari, Ugo; Rolim, José D. P.; Welzl, Emo (eds.). Proceedings of the 27th International Colloquium on Automata, Languages and Programming. pp. 61–72. ISBN 978-3-540-67715-4.
Henzinger, Monika R.; Klein, Philip; Rao, Satish; Subramanian, Sairam (1997). "Faster Shortest-Path Algorithms for Planar Graphs". Journal of Computer and System Sciences. 55 (1): 3–23. doi:10.1006/jcss.1997.1493.
Johnson, Donald B. (1977). "Efficient algorithms for shortest paths in sparse networks". Journal of the ACM. 24 (1): 1–12. doi:10.1145/321992.321993. S2CID 207678246.
Johnson, Donald B. (December 1981). "A priority queue in which initialization and queue operations take $O (log log D)$ time". Mathematical Systems Theory. 15 (1): 295–309. doi:10.1007/BF01786986. MR 0683047. S2CID 35703411.
Karlsson, Rolf G.; Poblete, Patricio V. (1983). "An $O (m log log D)$ algorithm for shortest paths". Discrete Applied Mathematics. 6 (1): 91–93. doi:10.1016/0166-218X(83)90104-X. MR 0700028.
Leyzorek, M.; Gray, R. S.; Johnson, A. A.; Ladew, W. C.; Meaker, S. R. Jr.; Petry, R. M.; Seitz, R. N. (1957). Investigation of Model Techniques — First Annual Report — 6 June 1956 — 1 July 1957 — A Study of Model Techniques for Communication Systems. Cleveland, Ohio: Case Institute of Technology.
Moore, E. F. (1959). "The shortest path through a maze". Proceedings of an International Symposium on the Theory of Switching (Cambridge, Massachusetts, 2–5 April 1957). Cambridge: Harvard University Press. pp. 285–292.
Pettie, Seth; Ramachandran, Vijaya (2002). "Computing shortest paths with comparisons and additions". Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 267–276. ISBN 978-0-89871-513-2.
Pettie, Seth (26 January 2004). "A new approach to all-pairs shortest paths on real-weighted graphs". Theoretical Computer Science. 312 (1): 47–74. doi:10.1016/s0304-3975(03)00402-x.
Pollack, Maurice; Wiebenson, Walter (March–April 1960). "Solution of the Shortest-Route Problem—A Review". Oper. Res. 8 (2): 224–230. doi:10.1287/opre.8.2.224. Attributes Dijkstra's algorithm to Minty ("private communication") on p. 225.
Schrijver, Alexander (2004). Combinatorial Optimization — Polyhedra and Efficiency. Algorithms and Combinatorics. Vol. 24. Springer. vol.A, sect.7.5b, p. 103. ISBN 978-3-540-20456-5.
Shimbel, Alfonso (1953). "Structural parameters of communication networks". Bulletin of Mathematical Biophysics. 15 (4): 501–507. Bibcode:1953BMaB...15..501S. doi:10.1007/BF02476438.
Shimbel, A. (1955). "Structure in communication nets". Proceedings of the Symposium on Information Networks. New York, NY: Polytechnic Press of the Polytechnic Institute of Brooklyn. pp. 199–203.
Thorup, Mikkel (1999). "Undirected single-source shortest paths with positive integer weights in linear time". Journal of the ACM. 46 (3): 362–394. doi:10.1145/316542.316548. S2CID 207654795.
Thorup, Mikkel (2004). "Integer priority queues with decrease key in constant time and the single source shortest paths problem". Journal of Computer and System Sciences. 69 (3): 330–353. doi:10.1016/j.jcss.2004.04.003.
Whiting, P. D.; Hillier, J. A. (March–June 1960). "A Method for Finding the Shortest Route through a Road Network". Operational Research Quarterly. 11 (1/2): 37–40. doi:10.1057/jors.1960.32.
Williams, Ryan (2014). "Faster all-pairs shortest paths via circuit complexity". Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC '14). New York: ACM. pp. 664–673. arXiv:1312.6680. doi:10.1145/2591796.2591811. MR 3238994.

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