//dijkstra.js
/*global adventurejs A*/

/**
 * 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;
};