Skip to content

Instantly share code, notes, and snippets.

@Dammmien
Last active April 8, 2018 21:30
Show Gist options
  • Star 2 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save Dammmien/765dd1c38d48df7254c2 to your computer and use it in GitHub Desktop.
Save Dammmien/765dd1c38d48df7254c2 to your computer and use it in GitHub Desktop.
Implementation of Dijkstra's algorithm in JavaScript
var nodes = [
{
links: [ 1, 3 ], // node 0 is linked to node 1 and 3
weightLinks: [ 5, 15 ], // the distance between node 0 and 1 is 5, between 0 and 3 is 15
distance: Infinity
}, {
links: [ 0, 2 ], // node 1 is linked to node 0 and 2
weightLinks: [ 5, 5, ], // the distance between node 1 and 0 is 5, between 1 and 2 is 5
distance: Infinity
},
...
];
function dijkstra( start ) {
nodes[ start ].distance = 0;
var queue = nodes.map( ( v, i ) => i );
while ( queue.length > 0 ) {
var queueIndex = undefined;
queue.reduce( function( minDist, nodeIndex, index ) {
queueIndex = nodes[ nodeIndex ].distance < minDist ? index : queueIndex;
return nodes[ nodeIndex ].distance < minDist ? nodes[ nodeIndex ].distance : minDist;
}, Infinity );
var nextIndex = queue.splice( queueIndex, 1 )[ 0 ];
nodes[ nextIndex ].links.forEach( function( childIndex, i ) {
var distance = nodes[ nextIndex ].distance + nodes[ nextIndex ].weightLinks[ i ];
if ( distance < nodes[ childIndex ].distance ) nodes[ childIndex ].distance = distance;
} );
}
};
dijkstra( 0 );
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment