# Implementation of Dijkstra's Algorithm in JavaScript that returns both shortestDist/shortestPaths

I decided to try to understand the basic idea behind Dijkstra's algorithm better so I implemented it in JavaScript (the only language I am proficient in as of now) so I could really see what was happening in the Chrome debugger.

I chose not to use a priority queue or a heap in my implementation, but I do return both the shortest paths and the shortest distances for each vertex from the source.

//my attempt at coding the wiki pseudocode version of Dijkstra in Javascript, that returns
//both the shortest paths AND shortest distances to each vertex from the source vertex input

var INFINITY = 1/0;

function DirectedGraph(){
this.vertices = {};
edges = edges || null;
this.vertices[name] = edges;
}
}

function findSmallest(dist, q) {
var min = Infinity;
var minNode;

for (var node in q) {
if (dist[node] <= min) {
min = dist[node]
minNode = node;
}
}

delete q[minNode]
return minNode;
}

function djikstra(graph, startVertex) {
var dist = {};
var prev = {};
var q = {};
var shortestPaths = {};

for (var vertex in graph.vertices) {
dist[vertex] = INFINITY;
prev[vertex] = null;
q[vertex] = graph.vertices[vertex];
shortestPaths[vertex] = [];
}

dist[startVertex] = 0;

while (Object.keys(q).length !== 0) {
var smallest = findSmallest(dist, q);
var smallestNode = graph.vertices[smallest]
//searches for the vertex u in the vertex set Q that has the least dist[smallest] value.

for (var neighbor in smallestNode) {
var alt = dist[smallest] + smallestNode[neighbor];
//smallestNode[neighbor] is the distance between smallest and neighbor
if (alt < dist[neighbor]) {
dist[neighbor] = alt
prev[neighbor] = smallest
}
}
}

getShortestPaths(prev, shortestPaths, startVertex, dist)

return {
shortestPaths: shortestPaths,
shortestDistances: dist
}
}

function getShortestPaths(previous, shortestPaths, startVertex, dist) { debugger
for (var node in shortestPaths) {
var path = shortestPaths[node];

while(previous[node]) {
path.push(node);
node = previous[node];
}

//gets the starting node in there as well if there was a path from it
if (dist[node] === 0) {
path.push(node);
}
path.reverse();
}
}

var graph = new DirectedGraph();

console.log(djikstra(graph, 'S'));

----------------->

{ shortestPaths:
{ S: [ 'S' ],
W: [ 'S', 'V', 'W' ],
V: [ 'S', 'V' ],
T: [ 'S', 'V', 'W', 'T' ] },
shortestDistances: { S: 0, W: 3, V: 1, T: 6 } }