var LineByLineReader = require('line-by-line'),
    lr1 = new LineByLineReader('inputFW.txt'),
    lr2 = new LineByLineReader('inputBFS.txt');

let inputFW = [];
let inputBFS = [];

lr1.on('line', function (line) {
  inputFW.push(line.split(' ').map(item => Number(item)));
});

lr2.on('line', function (line) {
  inputBFS.push(line.split(' ').map(item => Number(item)));
});

var pathMatrix = [];
var output = [];

function floydWarchallAlgorithm(input) {
  let nodesNr = input[0][0];
  let edgeNr = input[0][1];
  output = new Array(nodesNr);
  pathMatrix = new Array(nodesNr);

  for(let i = 0; i < nodesNr; i++) {
    output[i] = new Array(nodesNr).fill(Infinity);
    pathMatrix[i] = new Array(nodesNr).fill(null);

    for(let j = 0; j < nodesNr; j++) {
      if(i === j) output[i][j] = 0;
    }
  }

  for(let i = 1; i <= edgeNr; i++) {
    output[input[i][0] - 1][input[i][1] - 1] = input[i][2];
    pathMatrix[input[i][0] - 1][input[i][1] - 1] = input[i][1] - 1;
  }

  for(let k = 0; k < nodesNr; k++) {
    for(let i = 0; i < nodesNr; i++) {
      for(let j = 0; j < nodesNr; j++) {
        let dist = output[i][j];
        let dist2 = output[i][k] + output[k][j];
        if(dist > dist2 || dist === Infinity) {
          output[i][j] = dist2;
          pathMatrix[i][j] = pathMatrix[i][k];
        }
      }
    }
  }
  output.forEach(item => console.log(item));
  console.log('- - - - - - - -');
  pathMatrix.forEach(item => console.log(item));
  console.log('- - - - - - - -');
  printSolution(nodesNr);
}

function printPath(source, target) {
  if(pathMatrix[source][target] === null) return [];
  let path = [source + 1];
  while(source !== target) {
    source = pathMatrix[source][target];
    path.push(source + 1);
  }
  return path.join('-');
}

function printSolution(nodesNr) {
  for(let i = 0; i < nodesNr; i++) {
    for(let j = 0; j < nodesNr; j++) {
      if(output[i][j] !== Infinity && output[i][j] !== 0) {
        console.log('d[' + Number(i+1) + ',' + Number(j+1) + '] = ' + output[i][j]);
        console.log('PATH: ' + printPath(i, j));
      }
    }
  }
}

function bfs(input, source, target) {
  let q = [ [source] ];
  let path = [];
  let node;

  while(q.length) {
    path = q.shift();
    node = path[path.length - 1];
    if(node === target) return path;

    for(let i = 1; i < input.length; i++) {
      if(input[i][0] === node) {
        let path2 = path.slice();
        path2.push(input[i][1]);
        q.push(path2);
      }
    }
  }
  return path;
}


lr1.on('end', function () {
  console.log('>>> FW');
  floydWarchallAlgorithm(inputFW);
});

lr2.on('end', function () {
  console.log('\n>>> BFS');
  console.log(bfs(inputBFS, 0, 11).reverse());
});