Dijkstra's Algorithm

Graphhard#11

Find shortest path using priority queue — weighted graphs

Ready

Step 1 of 0

Speed

Algorithm Code

1function dijkstra(graph, start, end) {
2  const dist = new Map();
3  const pq = [[0, start]]; // [distance, node]
4  dist.set(start, 0);
5  while (pq.length > 0) {
6    pq.sort((a,b) => a[0] - b[0]);
7    const [d, u] = pq.shift();
8    if (u === end) return d;
9    for (const [v, w] of graph[u]) {
10      const nd = d + w;
11      if (nd < (dist.get(v) ?? Infinity)) {
12        dist.set(v, nd);
13        pq.push([nd, v]);
14      }
15    }
16  }
17  return Infinity;
18}

Best

O(V + E log V)

Average

O(V + E log V)

Worst

O(V²)

Space

O(V)

About Dijkstra's Algorithm

Dijkstra's algorithm finds the shortest path from a source to all other vertices in a weighted graph with non-negative edge weights. It uses a priority queue to always process the nearest unvisited vertex. The foundation of GPS navigation and network routing protocols.

Time Complexity: Best: O(V + E log V), Average: O(V + E log V), Worst: O(V²). Space: O(V).

Dijkstra's Algorithm

Graphhard#11

Find shortest path using priority queue — weighted graphs

Ready

Step 1 of 0

Speed

Algorithm Code

1function dijkstra(graph, start, end) {
2  const dist = new Map();
3  const pq = [[0, start]]; // [distance, node]
4  dist.set(start, 0);
5  while (pq.length > 0) {
6    pq.sort((a,b) => a[0] - b[0]);
7    const [d, u] = pq.shift();
8    if (u === end) return d;
9    for (const [v, w] of graph[u]) {
10      const nd = d + w;
11      if (nd < (dist.get(v) ?? Infinity)) {
12        dist.set(v, nd);
13        pq.push([nd, v]);
14      }
15    }
16  }
17  return Infinity;
18}

Best

O(V + E log V)

Average

O(V + E log V)

Worst

O(V²)

Space

O(V)

About Dijkstra's Algorithm

Time Complexity: Best: O(V + E log V), Average: O(V + E log V), Worst: O(V²). Space: O(V).