Code Review Stack Exchange is a question and answer site for peer programmer code reviews. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I decided to try to understand the basic idea behind Dijkstra's algorithm better so I implemented it in JavaScript (the only language I am proficient in as of now) so I could really see what was happening in the Chrome debugger.

I chose not to use a priority queue or a heap in my implementation, but I do return both the shortest paths and the shortest distances for each vertex from the source.

//my attempt at coding the wiki pseudocode version of Dijkstra in Javascript, that returns
//both the shortest paths AND shortest distances to each vertex from the source vertex input

var INFINITY = 1/0;

function DirectedGraph(){
  this.vertices = {};
  this.addVertex = function(name, edges){
    edges = edges || null;
    this.vertices[name] = edges;
  }
}

function findSmallest(dist, q) { 
  var min = Infinity;
  var minNode;

  for (var node in q) {
    if (dist[node] <= min) {
      min = dist[node]
      minNode = node;
    }
  }

  delete q[minNode]
  return minNode;
}

function djikstra(graph, startVertex) { 
  var dist = {};
  var prev = {};
  var q = {};
  var shortestPaths = {};

  for (var vertex in graph.vertices) {
    dist[vertex] = INFINITY;
    prev[vertex] = null;
    q[vertex] = graph.vertices[vertex];
    shortestPaths[vertex] = [];
  }

  dist[startVertex] = 0;

  while (Object.keys(q).length !== 0) {
    var smallest = findSmallest(dist, q);
    var smallestNode = graph.vertices[smallest] 
    //searches for the vertex u in the vertex set Q that has the least dist[smallest] value.

    for (var neighbor in smallestNode) {
      var alt = dist[smallest] + smallestNode[neighbor];
      //smallestNode[neighbor] is the distance between smallest and neighbor
      if (alt < dist[neighbor]) {
        dist[neighbor] = alt
        prev[neighbor] = smallest
      }
    }
  }

  getShortestPaths(prev, shortestPaths, startVertex, dist)

  return {
    shortestPaths: shortestPaths,
    shortestDistances: dist
  }
}

function getShortestPaths(previous, shortestPaths, startVertex, dist) { debugger
  for (var node in shortestPaths) {
    var path = shortestPaths[node];

    while(previous[node]) {
      path.push(node);
      node = previous[node];
    }

    //gets the starting node in there as well if there was a path from it
    if (dist[node] === 0) {
      path.push(node);
    } 
    path.reverse();
  }
}

var graph = new DirectedGraph();

graph.addVertex('S', {V: 1, W: 4});
graph.addVertex('W', {T: 3});
graph.addVertex('V', {W: 2, T: 6});
graph.addVertex('T');


console.log(djikstra(graph, 'S'));


----------------->

{ shortestPaths: 
   { S: [ 'S' ],
     W: [ 'S', 'V', 'W' ],
     V: [ 'S', 'V' ],
     T: [ 'S', 'V', 'W', 'T' ] },
  shortestDistances: { S: 0, W: 3, V: 1, T: 6 } }
share|improve this question
    
I used you implementation as a starting point to implement on my own gist.github.com/skeep/6cdfa9de0a408b7af78ba496e90ea53a – skeep Sep 21 at 18:33

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.