مسئله کوتاه ترین مسیر (Shortest Path Problem)، در ریاضیات (Mathematics)
انواع روش های بهینه سازی (Optimization Methods) را در آموزش زیر شرح دادیم :
مسئله کوتاه ترین مسیر (Shortest Path Problem) :
📌 معرفی
مسئله کوتاه ترین مسیر (Shortest Path Problem) یکی از اساسی ترین مسائل در نظریه گراف و تحقیق در عملیات است. هدف یافتن مسیری بین دو گره (مبدأ و مقصد) است که مجموع هزینه (یا زمان، فاصله) یال های آن کمینه شود.
🔧 الگوریتم های اصلی
الگوریتم دیکسترا (Dijkstra): برای گراف های با وزن غیرمنفی. پیچیدگی
\[ O(V^2) \]یا
\[ O(E + V \log V) \]با استفاده از heap.
الگوریتم بلمن-فورد (Bellman-Ford): برای گراف های با وزن منفی (تشخیص سیکل منفی). پیچیدگی
\[ O(VE) \].
الگوریتم فلوید-وارشال (Floyd-Warshall): یافتن کوتاه ترین مسیر بین همه جفت گره ها. پیچیدگی
\[ O(V^3) \].
الگوریتم A* (A-star): با استفاده از هیوریستیک برای هدایت جستجو (در هوش مصنوعی).
📐 فرمول بندی ریاضی (مدل برنامه ریزی خطی)
\[ \min \sum_{(i,j) \in A} c_{ij} x_{ij} \] \[ \text{s.t.} \quad \sum_{j} x_{sj} - \sum_{j} x_{js} = 1 \] \[ \quad \sum_{j} x_{jt} - \sum_{j} x_{tj} = -1 \] \[ \quad \sum_{j} x_{ij} - \sum_{j} x_{ji} = 0 \quad \forall i \neq s,t \] \[ \quad 0 \leq x_{ij} \leq 1, \quad x_{ij} \in \{0,1\} \]که
\[ x_{ij} \]نشان دهنده استفاده از یال
\[ (i,j) \]در مسیر است.
