Dijkstra

by Paco86

JavaScript

var graph = {};
graph['start'] = {};
graph['start']['a'] = 6;
graph['start']['b'] = 2;

graph['a'] = {};
graph['a']['fin'] = 1;

graph['b'] = {};
graph['b']['a'] = 3;
graph['b']['fin'] = 5;

graph['fin'] = {};


var costs = {};
costs['a'] = 6;
costs['b'] = 2;
costs['fin'] = 999;


var parents = {};
parents['a'] = 'start';
parents['b'] = 'start';
parents['fin'] = 'None';

var processed = [];
var totalCost;

function getLowestNode(costs){
  var node, cost = 999999;
  for(let key in costs){
  	if(cost > costs[key] && processed.indexOf(key) === -1){
    	cost = costs[key];
      node = key;
    }
  }
  
  return node;
}

var node = getLowestNode(costs);

while(node !== undefined){

	totalCost = costs[node];
	var neighbors = graph[node];
  for(let key in neighbors){
  	var newCost = totalCost + neighbors[key];
    if(costs[key] > newCost){
    	costs[key] = newCost;
      parents[key] = node
    }
  }
  processed.push(node);
  
  node = getLowestNode(costs);
}

alert(totalCost)