Module: 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.
Parameters:
Name Type Description
src Number Source node.
dest Number Destination node.
graph Array A distance matrix of the graph.
Source:
Returns:
The shortest distance between two nodes.
Type
Number
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