graphs/shortest-path/floyd-warshall

Floyd-Warshall algorithm. Finds the shortest path between each two vertices.

Complexity: O(|V|^3) where V is the number of vertices.

Source:

graphs/shortest-path/floyd-warshall.js, line 36

Parameters:

Name	Type	Description
`graph`	`Array`	A distance matrix of the graph.

Returns:

Type:: Array

Array which contains the shortest distance between each two vertices.

Example

var floydWarshall =
require('path-to-algorithms/src/graphs/shortest-path/floyd-warshall').floydWarshall;
var distMatrix =
   [[Infinity, 7,        9,       Infinity,  Infinity, 16],
    [7,        Infinity, 10,       15,       Infinity, Infinity],
    [9,        10,       Infinity, 11,       Infinity, 2],
    [Infinity, 15,       11,       Infinity, 6,        Infinity],
    [Infinity, Infinity, Infinity, 6,        Infinity, 9],
    [16,       Infinity, 2,        Infinity, 9,        Infinity]];

// [ [ 0, 7, 9, 20, 20, 11 ],
//   [ 7, 0, 10, 15, 21, 12 ],
//   [ 9, 10, 0, 11, 11, 2 ],
//   [ 20, 15, 11, 0, 6, 13 ],
//   [ 20, 21, 11, 6, 0, 9 ],
//   [ 11, 12, 2, 13, 9, 0 ] ]
var shortestDists = floydWarshall(distMatrix);