3
\$\begingroup\$

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 } }
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.