یادداشت کامل الگوریتم

الگوریتم Dijkstra

Dijkstra's Algorithm

Dijkstra کوتاه‌ترین مسیر از یک مبدأ را در گراف با edgeهای وزن غیرمنفی پیدا می‌کند؛ هر بار Node حل‌نشده با کمترین distance فعلی انتخاب و relax می‌شود.

نوعالگوریتمدستهگراف‌هاسطحپیشرفتهپیچیدگی معمولO((V+E) log V) with heap

جواب کوتاه و حرفه‌ای

اول این مفهوم را در ذهن نگه دار

توضیح ساده

چطور کار می‌کند؟ ساده و مرحله‌ای

distance مبدأ را 0 و بقیه را infinity قرار بده.

با Min Priority Queue ارزان‌ترین Node را بردار و اگر مسیر u→v distance بهتری داد، v را relax و به‌روزرسانی کن.

روند اجرا

الگوریتم را به شکل تصمیم‌های پشت سر هم بخوان

مشخص کن گراف directed/undirected و weighted/unweighted است.

representation گراف را انتخاب کن.

state الگوریتم و حالت disconnected/cycle را صریح مدیریت کن.

یک مثال کوچک برای فهم بهتر

یک ورودی خیلی کوچک را دستی اجرا کن و بعد از هر عملیات مهم state را بنویس. برای الگوریتم Dijkstra هدف این است که invariant را ببینی، نه اینکه کد را حفظ کنی.

پیاده‌سازی خوانا با JavaScriptJavaScript

// Pseudocode-like JavaScript. Use a real min-heap in production.
function dijkstra(graph, start) {
  const dist = new Map([[start, 0]]);
  const pq = [[0, start]];

  while (pq.length) {
    pq.sort((a, b) => a[0] - b[0]);
    const [cost, node] = pq.shift();
    if (cost !== dist.get(node)) continue;

    for (const [next, weight] of graph[node] ?? []) {
      const candidate = cost + weight;
      if (candidate < (dist.get(next) ?? Infinity)) {
        dist.set(next, candidate);
        pq.push([candidate, next]);
      }
    }
  }
  return dist;
}

این کد را چطور بخوانی؟

syntax را حفظ نکن. stateای را که در هر خط تغییر می‌کند دنبال کن و آن را به invariant توضیح‌داده‌شده در بالا وصل کن.

پیچیدگی

O((V+E) log V) with heap

این Complexity را حفظی نگو. اول مشخص کن مربوط به کدام عملیات یا بعد ورودی است؛ بعد هزینه را از روی loopها، عمق recursion، عملیات ساختمان داده و فرض‌های preprocessing نتیجه بگیر.

چه زمانی استفاده کنیم؟

موارد مناسب

فقط وقتی assumptionهای الگوریتم با مسئله گراف هماهنگ است از آن استفاده کن.

اشتباهات رایج

کجا معمولاً اشتباه می‌کنیم؟

استفاده با وزن منفی.
نادیده گرفتن entryهای قدیمی در Heap وقتی decrease-key مستقیم نداریم.

در مصاحبه چطور توضیح بدهیم؟

مدل یک پاسخ حرفه‌ای

شرط وزن غیرمنفی و مفهوم Relaxation را حتماً بگو. با Binary Heap و adjacency list پیچیدگی رایج O((V+E) log V) است.

مسئله→ایده اصلی→Invariant / State→Big-O→Trade-off

چند سؤال مصاحبه‌ای سریع

الگوریتم Dijkstra چه مسئله‌ای را حل می‌کند؟

درباره Complexity چه چیزی باید بگویم؟

پیچیدگی معمول اینجا O((V+E) log V) with heap است، اما جواب کامل باید این هزینه را به representation، constraint ورودی و عملیات غالب وصل کند.

رایج‌ترین اشتباه چیست؟

استفاده با وزن منفی.

موضوعات مرتبط برای ادامه مطالعهنمایش گرافDFS/BFSPriority Queue

// Pseudocode-like JavaScript. Use a real min-heap in production. function dijkstra(graph, start) { const dist = new Map([[start, 0]]); const pq = [[0, start]]; while (pq.length) { pq.sort((a, b) => a[0] - b[0]); const [cost, node] = pq.shift(); if (cost !== dist.get(node)) continue; for (const [next, weight] of graph[node] ?? []) { const candidate = cost + weight; if (candidate < (dist.get(next) ?? Infinity)) { dist.set(next, candidate); pq.push([candidate, next]); } } } return dist; }