ALGORITHMUS-LESENOTIZ

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.

TYPAlgorithmusKATEGORIEGraphsTIEFEFortgeschrittenTYPISCHE KOMPLEXITÄTO((V+E) log V) with heap

KURZE INTERVIEWANTWORT

Beginne mit diesem mentalen Modell

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.

EINFACHE ERKLÄRUNG

So funktioniert es – ohne unnötigen Jargon

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.

AUSFÜHRUNG

Lies den Algorithmus als Folge von Entscheidungen

Define directed/undirected and weighted/unweighted assumptions.

Choose the graph representation.

Track algorithm state and handle disconnected/cyclic cases explicitly.

Ein kleines Beispiel als Orientierung

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.

LESBARE JAVASCRIPT-IMPLEMENTIERUNGJavaScript

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

So liest du diesen Code

Lerne die Syntax nicht auswendig. Folge dem Zustand, der sich in jeder Zeile ändert, und verbinde ihn mit der oben beschriebenen Invariante.

KOMPLEXITÄT

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.

WANN EINSETZEN

Gut geeignet

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

HÄUFIGE FEHLER

Was typischerweise schiefgeht

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

SO ERKLÄRST DU ES IM INTERVIEW

Struktur einer professionellen Antwort

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).

Problem→Kernidee→Invariante / Zustand→Big-O→Trade-off

SCHNELLER INTERVIEW-CHECK

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.

Was sollte ich zur Komplexität erwähnen?

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.

Was ist der häufigste Fehler?

Using it with negative edge weights.

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