graph

by María Fernández

JavaScript

//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) {
  	debugger;
    dist[vertex] = INFINITY;
    prev[vertex] = null;
    q[vertex] = graph.vertices[vertex];
    shortestPaths[vertex] = [];
  }
	debugger;
  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
      }
    }
  }

  var shortestPaths = getShortestPaths(prev, startVertex, dist)

  return {
    shortestPaths: shortestPaths,
    shortestDistances: dist
  }
}

function getShortestPaths(previous, startVertex, dist) {
var shortestPaths = {};
	Object.keys(dist).forEach(function(nodeName) {
  	if(dist[nodeName] !== Infinity) {
    	var destinyNodeName = nodeName;
    	var path = [];
      while(previous[nodeName]) {
      	path.push(nodeName);
        nodeName = previous[nodeName];
      }
      if(dist[nodeName] === 0) {
      	path.push(nodeName);
      }
     ...