← Index

Graphs

Dijkstra's Algorithm

Shortest path in a weighted graph — always expand the closest node.

What it is

Dijkstra's finds the shortest path from a start node to every other node when edges have weights (costs) and none are negative. It's BFS's smarter sibling: instead of exploring in arrival order, it always expands whichever unvisited node currently has the smallest known distance — which is exactly what a min-heap (see heap.js) is good at giving you fast.

Real-world examples

• Turn-by-turn GPS navigation — finding the fastest route when roads have different travel times, not just different hop counts.
• Choosing the cheapest sequence of flight connections when each leg has a different price.

Where you've probably used this already

• Literally how Google/Apple Maps and most routing engines compute 'shortest route' when distances/times vary per edge.
• Network routing protocols (OSPF) picking the lowest-latency path between routers.
• Any 'cheapest way to get from A to B' feature where the connections have different costs — flight/train fare finders, game AI pathfinding (a relative of A*).

Complexity

Code

// Dijkstra's Algorithm — shortest path in a WEIGHTED graph (no negative
// weights). Like BFS, but instead of "next in line" it always expands
// the closest unvisited node first — that's why a min-heap/priority
// queue is the natural fit (see heap.js).
//
// This version uses a simple array scan for the "pick smallest" step
// instead of a real heap, to keep the shape easy to read on a phone.

function dijkstra(graph, start) {
  const distances = {};
  const visited = new Set();
  const previous = {};

  for (const node in graph) distances[node] = Infinity;
  distances[start] = 0;

  while (visited.size < Object.keys(graph).length) {
    // pick the unvisited node with the smallest known distance
    let closest = null;
    for (const node in distances) {
      if (visited.has(node)) continue;
      if (closest === null || distances[node] < distances[closest]) {
        closest = node;
      }
    }
    if (closest === null || distances[closest] === Infinity) break;

    visited.add(closest);

    for (const neighbor in graph[closest]) {
      const newDist = distances[closest] + graph[closest][neighbor];
      if (newDist < distances[neighbor]) {
        distances[neighbor] = newDist;
        previous[neighbor] = closest;
      }
    }
  }

  return { distances, previous };
}

function pathTo(previous, target) {
  const path = [target];
  let current = target;
  while (previous[current]) {
    current = previous[current];
    path.unshift(current);
  }
  return path;
}

// --- Example Usage: a tiny road network with travel times (minutes) ---
const roads = {
  A: { B: 4, C: 1 },
  B: { A: 4, D: 1 },
  C: { A: 1, D: 5, E: 8 },
  D: { B: 1, C: 5, E: 2 },
  E: { C: 8, D: 2 },
};

const { distances, previous } = dijkstra(roads, "A");
console.log("Shortest distances from A:", distances);
// { A: 0, B: 4, C: 1, D: 5, E: 7 }
console.log("Shortest path A -> E:", pathTo(previous, "E"));
// [ 'A', 'B', 'D', 'E' ]

// This is, literally, "get directions" — Google/Apple Maps, network
// routing protocols (OSPF), and flight-connection price finders all
// run some flavor of this.