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 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 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 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 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 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 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 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 commented Feb 1, 2019

Thank you so much. I readed Grokking Algorithms yesterday 👍

@matonny

This comment has been minimized.

Copy link

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 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 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
You can’t perform that action at this time.