Floyd Warshall algorithm implementation

floyd-warshall.js

// Floyd Warshall algorithm implementation

/* Floyd Warshall algorithm is an algorithm for finding shortest paths in a weighted graph */

const min = (a, b) => a < b ? a : b

const warshall = graph => {
  const len = graph.length
  const myGraph = []

  // Clone an array to avoid changing of initial graph
  for (let i = 0; i < len; i++) {
    myGraph[i] = [...graph[i]]
  }

  for (let k = 0; k < len; ++k)
    for (let i = 0; i < len; ++i)
      for (let j = 0; j < len; ++j)
        myGraph[i][j] = min(myGraph[i][j], myGraph[i][k] + myGraph[k][j])


  return myGraph
}



/* test */
/*
  a --> c    3
  b --> a    2
  c --> b    7
  c --> d    1
  d --> a    6
*/

const myGraph = [
  [0,        Infinity, 3,        Infinity],
  [2,        0,        Infinity, Infinity],
  [Infinity, 7,        0,        1],
  [6,        Infinity, Infinity, 0]
]

const res = warshall(myGraph)

console.log(res)

/*
  [
    [ 0, 10, 3, 4 ],
    [ 2, 0, 5, 6 ],
    [ 7, 7, 0, 1 ],
    [ 6, 16, 9, 0 ]
   ]
*/