graphs/shortest-path/dijkstra

Dijkstra's shortest path algorithm. Finds the minimum distance between two given nodes using a distance matrix.

For the implementation is not used the most suitable data structure (Fibonacci heap) but the Binary heap gives also good results.

Time complexity: O(|E|+|V|log(|V|)) where V and E are the number of vertices and edges respectively.

Source:

graphs/shortest-path/dijkstra.js, line 66

Parameters:

Name	Type	Description
`src`	`Number`	Source node.
`dest`	`Number`	Destination node.
`graph`	`Array`	A distance matrix of the graph.

Returns:

Type:: Number

The shortest distance between two nodes.

Example

var dijkstra =
require('path-to-algorithms/src/graphs/shortest-path/dijkstra').dijkstra;
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]];
var shortestDist = dijkstra(0, 2, distMatrix); // 9