Graph Algorithms

Dijkstra's Algorithm

What is Dijkstra's Algorithm?

Dijkstra's algorithm finds the shortest-distance path from a single start vertex to every other vertex in a weighted graph — "shortest" meaning the smallest total edge weight along the path, not the fewest edges (which is what plain BFS finds on an unweighted graph). It requires every edge weight to be non-negative; a single negative weight can break its core assumption and produce wrong answers.

How Does It Work?

The algorithm keeps a tentative distance for every vertex, starting at 0 for the source and infinity for everything else. At each step, it finalizes whichever unvisited vertex currently has the smallest tentative distance — once a vertex is finalized, its distance is guaranteed correct and will never be revised again. Then it "relaxes" every edge out of that vertex: for each neighbor, if going through the just-finalized vertex would produce a shorter distance than what's currently recorded, the neighbor's distance is updated.

The key insight behind why picking the smallest unvisited distance is always safe: since every edge weight is non-negative, any path to that vertex through a still-unvisited (and therefore farther-or-equal) vertex could only be equal or longer. There's no way a shortcut could still be waiting to be discovered. That guarantee is exactly what breaks down if a negative edge weight is allowed — a path through a vertex that currently looks farther away could later turn out shorter, and algorithms like Bellman-Ford exist specifically to handle that case.

Shortest distances from A — the path A→C→B→D (1+1+3=5) beats A→B→D directly (3+3=6)

Algorithm Steps

Set the start vertex's distance to 0, and every other vertex's distance to infinity
While unvisited vertices remain, repeat:
- Pick the unvisited vertex with the smallest tentative distance and mark it finalized
- For each of its neighbors, if the path through this vertex is shorter than the neighbor's current recorded distance, update it (this is a "relaxation")
Once every reachable vertex is finalized, each vertex's recorded distance is its true shortest distance from the start
To reconstruct the actual shortest path to any vertex, follow the chain of "came from" pointers recorded during relaxation, back to the start

Time Complexity

Time Complexity: O((V + E) log V) with a binary heap priority queue — each vertex is extracted once and each edge triggers at most one relaxation, both at logarithmic cost.
Space Complexity: O(V) — for the distance array, the previous-vertex pointers, and the priority queue.

Time Complexity Analysis

Dijkstra's algorithm (typically implemented with a min-priority-queue for efficiency) is the standard tool behind GPS and mapping route-finding, network routing protocols that pick the cheapest path between routers, and any scenario where "cheapest route through a weighted network" needs an exact answer rather than an approximation.

Daily DSA Challenge by Scale Engineer

Find the shortest weighted-distance path from a start vertex to every other vertex

Directed graph

Build a weighted graph, pick a start vertex, and run Dijkstra

Graph

Add a vertex to begin

UnvisitedFinalizedCurrently finalized / edge relaxedShortest path

Test Your Knowledge before moving forward!

Dijkstra's Algorithm Quiz

How it works:

+1 point for each correct answer
0 points for wrong answers
-0.5 point penalty for viewing explanations
Earn stars based on your final score (max 5 stars)

Dijkstra's Algorithm Implementation

// Greedy relaxation: since all weights are non-negative, always finalizing
// the closest unvisited vertex guarantees its distance can never improve.
function dijkstra(vertices, adjList, start) {
  const dist = {};
  const prev = {};
  const visited = new Set();
  vertices.forEach((v) => (dist[v] = Infinity));
  dist[start] = 0;

  while (visited.size < vertices.length) {
    // Pick the unvisited vertex with the smallest tentative distance
    let u = null;
    let best = Infinity;
    for (const v of vertices) {
      if (!visited.has(v) && dist[v] < best) {
        best = dist[v];
        u = v;
      }
    }
    if (u === null) break; // remaining vertices are unreachable

    visited.add(u);

    for (const { to, weight } of adjList[u] || []) {
      if (visited.has(to)) continue;
      const candidate = dist[u] + weight;
      if (candidate < dist[to]) {
        dist[to] = candidate; // relax the edge
        prev[to] = u;
      }
    }
  }

  return { dist, prev };
}

function reconstructPath(prev, start, target) {
  const path = [];
  let current = target;
  while (current !== undefined && current !== start) {
    path.unshift(current);
    current = prev[current];
  }
  if (current !== start) return null; // unreachable
  path.unshift(start);
  return path;
}

// Usage example
const adjList = {
  A: [{ to: "B", weight: 4 }, { to: "C", weight: 1 }],
  B: [{ to: "A", weight: 4 }, { to: "C", weight: 2 }, { to: "D", weight: 5 }],
  C: [{ to: "A", weight: 1 }, { to: "B", weight: 2 }, { to: "D", weight: 8 }],
  D: [{ to: "B", weight: 5 }, { to: "C", weight: 8 }],
};
const { dist, prev } = dijkstra(["A", "B", "C", "D"], adjList, "A");
reconstructPath(prev, "A", "D"); // ["A", "C", "B", "D"]

Done With the Learning

Mark Dijkstra's Algorithm as done and view it on your dashboard

Explore Other Topics

Kruskal's Algorithm

Prim's Algorithm

Topological Sort

Breadth-First Search

Depth-First Search

Adjacency List

Adjacency Matrix