ملاحظة قراءة الخوارزمية

Dijkstra's Algorithm

Dijkstra finds single-source shortest paths in a graph with non-negative edge weights by repeatedly finalizing the unsettled node with the smallest known distance.

النوعخوارزميةالفئةGraphsالعمقمتقدمالتعقيد المعتادO((V+E) log V) with heap

إجابة مقابلة قصيرة

ابدأ بهذا النموذج الذهني

Dijkstra finds single-source shortest paths in a graph with non-negative edge weights by repeatedly finalizing the unsettled node with the smallest known distance.

شرح مبسط

كيف يعمل، بلا مصطلحات زائدة

Initialize source distance to 0 and others to infinity.

Use a min-priority queue; when an edge u→v gives a cheaper route, relax v and update its distance.

التنفيذ

اقرأ الخوارزمية كسلسلة من القرارات

Define directed/undirected and weighted/unweighted assumptions.

Choose the graph representation.

Track algorithm state and handle disconnected/cyclic cases explicitly.

مثال صغير لتحتفظ به في ذهنك

Read a tiny input by hand and write down the state after every important operation. For Dijkstra's Algorithm, the goal is to make the invariant visible rather than to memorize code.

تطبيق JavaScript قابل للقراءةJavaScript

// 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;
}

كيف تقرأ هذا الكود

لا تحفظ الصياغة. تتبع الحالة التي تتغير في كل سطر واربطها بالثابت الموضح أعلاه.

التعقيد

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

Do not quote this complexity mechanically. Ask which operation or input dimension it describes, then derive the cost from the loops, recursion depth, data-structure operations and any preprocessing assumptions.

متى تستخدمه

مناسب لـ

Use the algorithm only when its graph assumptions match the problem.

أخطاء شائعة

ما الذي يسوء عادةً

Using it with negative edge weights.
Forgetting stale entries when using a heap without decrease-key.

كيف تشرحه في المقابلة

صيغة إجابة احترافية

State the non-negative-weight requirement and explain relaxation. With a binary heap and adjacency list, a common complexity is O((V+E) log V).

المشكلة→الفكرة الأساسية→الثابت / الحالة→Big-O→المفاضلة

فحص سريع للمقابلة

What problem does Dijkstra's Algorithm solve?

Dijkstra finds single-source shortest paths in a graph with non-negative edge weights by repeatedly finalizing the unsettled node with the smallest known distance.

ماذا يجب أن أذكر عن التعقيد؟

Its typical cost here is O((V+E) log V) with heap, but a complete answer should connect that cost to the representation, input constraints and the dominant operations.

ما الخطأ الأكثر شيوعاً؟

Using it with negative edge weights.

متابعة القراءةGraph representationDFS/BFSPriority queues

// 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; }