//dijkstra.js
/*global adventurejs A*/ 
"use strict";

/**
 * A <a href="https://en.wikipedia.org/wiki/Pathfinding">pathfinding</a> function used to determine whether travel between two given locations is possible. 
 * Based on 
 * <a href="https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm">Dijkstra's algorithm</a>, 
 * specifically adapted from <a href="https://gist.github.com/jpillora/7382441">jpillora's dijkstra.js</a>.
 * @method adventurejs#dijkstra
 * @memberOf adventurejs
 * @param {Array} graph 
 * @param {String} s 
 * @returns {Object}
 */
adventurejs.dijkstra = function Adventurejs_dijkstra( graph, s ) 
{

  var solutions = {};
  solutions[s] = [];
  solutions[s].dist = 0;
  
  while(true) 
  {
    var parent = null;
    var nearest = null;
    var dist = Infinity;
    
    //for each existing solution
    for(var n in solutions) 
    {
      if(!solutions[n]) 
      { 
        continue; 
      }
      var ndist = solutions[n].dist;
      var adj = graph[n];

      //for each of its adjacent nodes...
      for(var a in adj) 
      {
        //without a solution already...
        if(solutions[a]) 
        { 
          continue; 
        }
        //choose nearest node with lowest *total* cost
        var d = adj[a] + ndist;
        if(d < dist) 
        {
          //reference parent
          parent = solutions[n];
          nearest = a;
          dist = d;
        }
      }
    }
    
    //no more solutions
    if(dist === Infinity) 
    {
      break;
    }
    
    //extend parent's solution path
    solutions[nearest] = parent.concat(nearest);
    //extend parent's cost
    solutions[nearest].dist = dist;
  }

return solutions;
}