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, root, target) {
  function neighbors([x, y]) {
    const candidates = [
      [x + 1, y],
      [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 start = [root]
  const frontier = [[evaluate(start), start]]
  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 (node.toString() === target.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"))
console.log(bfs(graph, [0, 0], [graph[0].length - 1, graph.length - 1]))

$ time node --use-strict path-sum.js
real   0m0.496s
user   0m0.646s
sys    0m0.000s

#!/usr/bin/env python
import os
import sys
from collections import defaultdict

def dijkstra(matrix):
    def neighbors(node):
        (x, y) = node
        n = []
        if x < len(matrix[0]) - 1:
            n.append((x + 1, y))
        if y < len(matrix) - 1:
            n.append((x, y + 1))
        return n

    def value(node):
        (x, y) = node
        return matrix[y][x]
    
    current = (0, 0)
    dest = (len(matrix[0]) - 1, len(matrix) - 1)
    unvisited = set((x, y) for x in range(dest[0] + 1) for y in range(dest[1] + 1))
    nodes = {}
    for node in unvisited: nodes[node] = sys.maxsize
    nodes[current] = value(current)

    while 1:
        for node in [n for n in neighbors(current) if n in unvisited]:
            distance = nodes[current] + value(node)
            if distance < nodes[node]:
                nodes[node] = distance

        unvisited.remove(current)
        if current == dest:
            break
        else:
            current = min((nodes[node], node) for node in unvisited)[1]

    return nodes[dest]

def main():
    matrix = []
    with open(os.path.join(os.path.dirname(__file__), "matrix.txt")) as matfile:
        for row in matfile:
            matrix.append([int(n) for n in row.split(',')])

    print(dijkstra(matrix))

if __name__ == "__main__": main()

$ time python3 minimal_path.py
real   0m4.587s
user   0m4.586s
sys    0m0.000s