const fs = require("fs")

function parseMatrix(matrix) {
  return matrix.toString().trim().split("\n").map((line) => {
    return line.split(",").map((c) => parseInt(c))
  })
}

function bfs(graph, sources, targets) {
  function neighbors([x, y]) {
    const candidates = [
      [x + 1, y],
      [x, y - 1],
      [x, y + 1]
    ]
    return candidates.filter(([x, y]) => {
      return x >= 0 && x < graph[0].length && y >= 0 && y < graph.length
    })
  }

  function evaluate(path) {
    return path.reduce((acc, [x, y]) => acc + graph[y][x], 0)
  }

  const frontier = []
  sources.forEach((source) => {
    const start = [source]
    frontier.push([evaluate(start), start])
  })
  const destinations = new Set()
  targets.forEach((target) => {
    destinations.add(target.toString())
  })
  const explored = new Set()
  while (frontier.length > 0) {
    let path = null
    let min = Infinity
    let index = -1
    frontier.forEach(([score, candidate], i) => {
      if (score < min) {
        min = score
        path = candidate
        index = i
      }
    })
    frontier.splice(index, 1)
    const node = path[path.length - 1]
    explored.add(node.toString())
    if (destinations.has(node.toString())) {
      return min
    }
    neighbors(node).forEach((neighbor) => {
      if (!explored.has(neighbor.toString())) {
        const newPath = path.slice()
        newPath.push(neighbor)
        frontier.push([evaluate(newPath), newPath])
      }
    })
  }
}

const graph = parseMatrix(fs.readFileSync(__dirname + "/matrix.txt"))
const sources = []
const targets = []
for (let i = 0; i < graph.length; i++) {
  sources.push([0, i])
  targets.push([graph[0].length - 1, i])
}
console.log(bfs(graph, sources, targets))

$ time node --use-strict path-sum.js
real   0m0.951s
user   0m1.133s
sys    0m0.047s

#!/usr/bin/env python2
import os
import heapq

def parse(matfile):
    return [[int(n) for n in row.split(',')] for row in matfile]

def distance(a, b):
    return sum(abs(a[i] - b[i]) for i in range(len(a)))

def astar(matrix, targets, sources):
    def neighbors(position):
        (x, y) = position
        candidates = [(x, y - 1), (x, y + 1), (x + 1, y)]
        return [(x, y) for (x, y) in candidates if x >= 0 and x < len(matrix)
                                               and y >= 0 and y < len(matrix[0])]

    def evaluate(path):
        f = sum(matrix[y][x] for (x, y) in path)
        h = min(distance(path[-1], target) for target in targets)
        return f + h

    targets = set(targets)
    frontier = set(sources)
    explored = set()
    frontier_queue = []
    for source in sources:
        path = [source]
        heapq.heappush(frontier_queue, (evaluate(path), path))

    while frontier:
        (_, path) = heapq.heappop(frontier_queue)
        frontier.remove(path[-1])
        explored.add(path[-1])
        if path[-1] in targets:
            return path
        for neighbor in neighbors(path[-1]):
            if neighbor not in frontier | explored:
                frontier.add(neighbor)
                new_path = path + [neighbor]
                heapq.heappush(frontier_queue, (evaluate(new_path), new_path))

def main():
    with open(os.path.join(os.path.dirname(__file__), "matrix.txt")) as matfile:
        matrix = parse(matfile)
    targets = [(len(row) - 1, y) for y, row in enumerate(matrix)]
    sources = [(0, y) for y, row in enumerate(matrix)]
    print(sum(matrix[y][x] for (x, y) in astar(matrix, targets, sources)))

if __name__ == "__main__": main()

$ time python3 path-sum.py
real   0m1.978s
user   0m1.970s
sys    0m0.008s