Finding Shortest Paths in Weighted Graphs with Dijkstras Algorithm in JavaScript

Breadth-First Search (BFS) finds the shortest path in unweighted graphs, but real-world routing problems—such as network latency minimization, road network navigation, and pipeline cost optimization—assign non-negative weights to graph edges.

Dijkstra's Algorithm solves the single-source shortest path problem on weighted directed or undirected graphs using greedy edge relaxation.

Example #

Finding the cheapest routing path from node 'A' across an adjacency graph:

const graph = {
  A: { B: 4, C: 2 },
  B: { A: 4, C: 1, D: 5 },
  C: { A: 2, B: 1, D: 8, E: 10 },
  D: { B: 5, C: 8, E: 2 },
  E: { C: 10, D: 2 }
};

Implementation #

function dijkstra(graph, startNode) {
  const distances = {};
  const visited = new Set();
  const nodes = Object.keys(graph);

  for (const node of nodes) {
    distances[node] = Infinity;
  }
  distances[startNode] = 0;

  while (visited.size < nodes.length) {
    // Find unvisited node with smallest known distance
    let currentNode = null;
    let smallestDistance = Infinity;

    for (const node of nodes) {
      if (!visited.has(node) && distances[node] < smallestDistance) {
        smallestDistance = distances[node];
        currentNode = node;
      }
    }

    if (currentNode === null) break;
    visited.add(currentNode);

    // Relax neighboring edges
    for (const [neighbor, weight] of Object.entries(graph[currentNode])) {
      const distanceThroughCurrent = distances[currentNode] + weight;
      if (distanceThroughCurrent < distances[neighbor]) {
        distances[neighbor] = distanceThroughCurrent;
      }
    }
  }

  return distances;
}

const shortestDistances = dijkstra(graph, 'A');
console.log(shortestDistances); // { A: 0, B: 3, C: 2, D: 8, E: 10 }

Complexity Analysis #

• Time Complexity: (O(V^2)) with array lookup, or (O((V + E) \log V)) when implemented with a binary min-heap priority queue.
• Space Complexity: (O(V)) to store distance tables and visited node sets.

Main Point: Dijkstra's algorithm uses greedy relaxation to determine optimal shortest paths in weighted graphs with non-negative edge costs.

Credits #

Photo by Kalist Strzalkowski on Unsplash

← Home