Algorithms
Logic
Based on the pseudocode at: https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
Please check the test cases for an example input.
function dijkstra(numberOfVertices, edges, source, target) {
if (target >= numberOfVertices) throw new Error('target outside available vertices');
if (source < 0 || numberOfVertices === 0) throw new Error('source outside available vertices');
const dist = {};
const prev = {};
const q = [];
for (let v = 0; v < numberOfVertices; v++) {
dist[v] = Infinity;
prev[v] = null;
q.push(v);
}
dist[source] = 0;
while (q.length) {
// Node with the least distance will be selected first
const u = q.reduce((minV, v) => dist[v] < dist[minV] ? v : minV );
if (u === target) break;
// Remove u from q
q.splice(q.indexOf(u), 1);
(edges[u] || [])
.forEach(edge => {
const alt = dist[u] + edge.cost;
if (alt < dist[edge.to]) {
dist[edge.to] = alt;
prev[edge.to] = u;
}
});
}
if (dist[target] === Infinity) return null;
const s = [];
let u = target;
while (prev[u] !== null) {
s.unshift(u);
u = prev[u];
}
s.unshift(u);
return s;
}const numberOfVertices = 5; // 0, 1, 2, 3, 4
const edges = {
0: [{ to: 1, cost: 2}],
1: [{ to: 0, cost: 1},
{ to: 2, cost: 3},
{ to: 3, cost: 10}],
3: [{ to: 4, cost: 2}]};
const start = 0;
const finish = 4;
describe("Examples", function() {
it("should return the best path", function() {
const path = dijkstra(numberOfVertices, edges, start, finish);
console.log(path);
Test.assertSimilar(path, [0, 1, 3, 4], "Returns the correct path");
});
it("should return null when no path is possible", function() {
const path = dijkstra(numberOfVertices + 1, edges, start, finish + 1);
console.log(path);
Test.assertEquals(path, null, "Returns null");
});
it("should throw an error if target is outside the available vertices", function() {
Test.expectError(() => dijkstra(numberOfVertices, edges, start, finish + 1));
});
it("should throw an error if source is outside the available vertices", function() {
Test.expectError(() => dijkstra(numberOfVertices, edges, start - 1, finish));
Test.expectError(() => dijkstra(0, edges, 0, 0));
});
});function sum(arr) {
return arr.reduce((sum, elem) => sum + elem, 0);
}describe("Sum", function(){
it("should sum correctly", function(){
Test.assertEquals(sum([5,2,1]), 8, "Sum equal to 8");
});
});