// Dijkstra's

function dijkstra(graph, src) {
  const dist = [], path = [], visited = [], N = graph.length;

  for (let i = 0; i < N; i++) {
    dist[i] = Infinity;
    visited[i] = false
    path[i] = []
  }

  dist[src] = 0

  for (let i = 0; i < N; i++) {
    let u = minDistances(dist, visited)
    visited[u] = true;

    for (let v = 0; v < N; v++) {
      if (visited[v] || !graph[u][v] || dist[u] === Infinity) continue
      if (dist[u] + graph[u][v] < dist[v]) {
        if (dist[v] !== Infinity) path[v].pop()
        dist[v] = dist[u] + graph[u][v]
        path[v].push(u)
        path[v].push(...path[u])
      }
    }
  }
  return [dist, path]
}

function minDistances(dist, visited) {
  let min = Infinity, minIndex = -1
  for (let v = 0; v < dist.length; v++) {
    if (visited[v] === false && dist[v] <= min) {
      min = dist[v]
      minIndex = v
    }
  }
  return minIndex
}

const matrix = [
  [0, 2, 4, 0, 0, 0],
  [0, 0, 1, 4, 2, 0],
  [0, 0, 0, 0, 3, 0],
  [0, 0, 0, 0, 0, 2],
  [0, 0, 0, 3, 0, 2],
  [0, 0, 0, 0, 0, 0]
]
const res = dijkstra(matrix, 0)
console.log(res)

// Dijkstra's

function dijkstra(source, adj) {
  const N = adj.size
  const dist = new Array(N).fill(Infinity)
  const visited = new Array(N).fill(false)
  dist[source] = 0

  for (let i = 0; i < N; i++) {
    const u = minDistance(dist, visited)
    visited[u] = true
    if (dist[u] === Infinity) continue
    for (let v of adj.get(u)) {
      if (visited[v.index]) continue
      if (dist[v.index] > dist[u] + v.weight) {
        dist[v.index] = dist[u] + v.weight
      }
    }
  }
  return dist
}

function minDistance(dist, visited) {
  let min = Infinity, minIndex = -1
  for (let i = 0; i < dist.length; i++) {
    if (!visited[i] && dist[i] < min) {
      min = dist[i]
      minIndex = i
    }
  }
  return minIndex
}

function buildAdj(graph) {
  const adj = new Map()
  for (let r = 0; r < graph.length; r++) {
    adj.set(r, new Set())
    for (let c = 0; c < graph[r].length; c++) {
      if (!graph[r][c]) continue
      adj.get(r).add({ index: c, weight: graph[r][c] })
    }
  }
  return adj
}

const matrix = [
  [0, 2, 4, 0, 0, 0],
  [0, 0, 1, 4, 2, 0],
  [0, 0, 0, 0, 3, 0],
  [0, 0, 0, 0, 0, 2],
  [0, 0, 0, 3, 0, 2],
  [0, 0, 0, 0, 0, 0]
]
const adj = buildAdj(matrix)
const res = dijkstra(0, adj)
console.log(res)