Dijkstra's Algorithm in Javascript using a weighted graph

dijkstra.js

const problem = {
  start: {A: 5, B: 2},
  A: {C: 4, D: 2},
  B: {A: 8, D: 7},
  C: {D: 6, finish: 3},
  D: {finish: 1},
  finish: {}
};

const lowestCostNode = (costs, processed) => {
  return Object.keys(costs).reduce((lowest, node) => {
    if (lowest === null || costs[node] < costs[lowest]) {
      if (!processed.includes(node)) {
        lowest = node;
      }
    }
    return lowest;
  }, null);
};

// function that returns the minimum cost and path to reach Finish
const dijkstra = (graph) => {

  // track lowest cost to reach each node
  const costs = Object.assign({finish: Infinity}, graph.start);

  // track paths
  const parents = {finish: null};
  for (let child in graph.start) {
    parents[child] = 'start';
  }

  // track nodes that have already been processed
  const processed = [];

  let node = lowestCostNode(costs, processed);

  while (node) {
    let cost = costs[node];
    let children = graph[node];
    for (let n in children) {
      let newCost = cost + children[n];
      if (!costs[n]) {
        costs[n] = newCost;
        parents[n] = node;
      }
      if (costs[n] > newCost) {
        costs[n] = newCost;
        parents[n] = node;
      }
    }
    processed.push(node);
    node = lowestCostNode(costs, processed);
  }

  let optimalPath = ['finish'];
  let parent = parents.finish;
  while (parent) {
    optimalPath.push(parent);
    parent = parents[parent];
  }
  optimalPath.reverse();

  const results = {
    distance: costs.finish,
    path: optimalPath
  };

  return results;
};

console.log(dijkstra(problem));

Hi, thank you so much for your easy to understand write up and the example code.
However, I noticed that the algorithm runs in an endless loop for a problem graph like this one:

const problem = {
    start: {A: 5, B: 2},
    A: {start: 1, C: 4, D: 2},
    B: {A: 8, D: 7},
    C: {D: 6, finish: 3},
    D: {finish: 1},
    finish: {}
};

I managed to prevent this by checking if n in children does not equal the start node name (in your case start). Nevertheless, there might be better ways ... . Feel free to check my solution in my fork, but I added some more things (including some logging to understand what is going on 😜).

Why the nested if statements on line 11/12? Why not a single if statement?

@MoeweX Dijkstra’s algorithm only works with directed acyclic graphs. Your graph is cyclic and your solution is not Dijkstra’s algorithm

Dijkstra's algorithm actually works just fine on cyclic graphs as long as there are no negative weights on the edges.

Could someone please explain the reduce block?

like
const lowestCostNode = (costs, processed) => {
return Object.keys(costs).reduce((lowest, node) => {
if (lowest === null || costs[node] < costs[lowest]) {
if (!processed.includes(node)) {
lowest = node;
}
}
return lowest;
}, null);
};

1st iteration it takes null as lowest and first key in the costs object as node and then what ?
costs of lowest in the subsequent iteration means what ? I just not getting the whole picture. Please explain.

Why not collapse

      if (!costs[n]) {
        costs[n] = newCost;
        parents[n] = node;
      }
      if (costs[n] > newCost) {
        costs[n] = newCost;
        parents[n] = node;
      }

to

      if (!costs[n] || costs[n] > newCost) {
        costs[n] = newCost;
        parents[n] = node;
      }

?

My implementation this algorithm by functional style: link to my repo

But I'm just a newbie. Maybe someone will correct me. Criticizes.

Thank you so much. I readed Grokking Algorithms yesterday 👍

Hello, I'm writing a research paper for school about the comparison the efficiency of Dijkstra's algorithm and genetic algorithms. I was wondering if I could use the code you provided? Obviously with a proper credit.

Thank you @stella-yc

In the while loop to get the path to the finish node I would change the push() method with unshift() so there is no need to use the reverse() method to get the correct order in the array

  while (parent) {
    optimalPath.unshift(parent);
    parent = parents[parent];
  }
  
  const results = {
    distance: costs.finish,
    path: optimalPath
  };

  return results;

};

My ruby implementation

Thank you @stella-yc

In the while loop to get the path to the finish node I would change the push() method with unshift() so there is no need to use the reverse() method to get the correct order in the array

  while (parent) {
    optimalPath.unshift(parent);
    parent = parents[parent];
  }
  
  const results = {
    distance: costs.finish,
    path: optimalPath
  };

  return results;

};

My ruby implementation

Changing the push to a unshift makes it almost (n) times slower;
https://stackoverflow.com/questions/12250697/time-complexity-of-unshift-vs-push-in-javascript

Based on the code above I wrote a Dijkrasta implementation in TypeScript that uses a Priorityqueue to optimize the runtime complexity of the algorithm. I also use an adapter to make it usable no matter how you store your graph. In case someone is interested: https://github.com/kaisnb/dijkstra-ts

The algorithm is visiting all the nodes , is there any way to find the smallest path without visiting let's say the other edges

@hamzalak Maybe you could remove all nodes that are not the finish node and that have no children before running the algorithm or as a check within the algorithm.

What about undirected graphs? How can we simplify the problem if we consider that all edges have the same cost (1)?

@thiagoarantes I think the algorithm still works with undirected graphs, but when calculating the shortest path, you only consider the outgoing direction. So for something like flight routing, segments between cities are always bidirectional, but we assume the shortest route will go toward the destination and never backtrack. Even if it did backtrack, it adds to the cost, so the direct route would be selected anyway.

If all edges have the same cost, the algorithm still works, you just optimize for number of segments versus the total cost. That's how it works for my application (routing messages in a P2P network). For my use case, there is no difference in cost to route from A to B versus A to C, so the cost is all 1, so the total number of segments will determine the total cost...A to Z to C would be 2 while A to B to C to Z would be 3.