Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Dijkstra's Algorithm in Javascript using a weighted graph
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));
@MoeweX

This comment has been minimized.

Copy link

@MoeweX MoeweX commented Jan 30, 2018

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 😜).

@kyeotic

This comment has been minimized.

Copy link

@kyeotic kyeotic commented Mar 9, 2018

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

@O4epegb

This comment has been minimized.

Copy link

@O4epegb O4epegb commented Apr 5, 2018

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

@sixhops

This comment has been minimized.

Copy link

@sixhops sixhops commented Aug 1, 2018

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

@recmach

This comment has been minimized.

Copy link

@recmach recmach commented Sep 14, 2018

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.

@webpepper

This comment has been minimized.

Copy link

@webpepper webpepper commented Sep 28, 2018

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;
      }

?

@Poletay

This comment has been minimized.

Copy link

@Poletay Poletay commented Nov 10, 2018

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

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

@Spike-86

This comment has been minimized.

Copy link

@Spike-86 Spike-86 commented Feb 1, 2019

Thank you so much. I readed Grokking Algorithms yesterday 👍

@matonny

This comment has been minimized.

Copy link

@matonny matonny commented Mar 1, 2019

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.

@johand

This comment has been minimized.

Copy link

@johand johand commented Apr 13, 2019

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

@galesky

This comment has been minimized.

Copy link

@galesky galesky commented Jan 16, 2020

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment