dijkstra.js

dijkstra.js

let G = [
[0,        2,         5,        Infinity], 
[2,        0,         Infinity, 7       ], 
[5,        Infinity,  0,        Infinity], 
[Infinity, 7,         Infinity, 0      ]];

let N = G.length;
let target = 3; // target is to visit 3rd
let distance = new Array(N).fill(Infinity);
let visited = new Array(N).fill(false);
distance[0] = 0;

while(visited[target] == false) {
	// 1 choose shortest non visited 
	let current = 0;
	let min = Infinity;
	for (let i = 0; i < N; i++) {
		if (distance[i] != Infinity && visited[i] == false) {
			if (distance[i] < min) {
				min = distance[i];
				current = i;
			}
		}
	}

	// 2 calculate neighbours and update distance
	let neighbours = G[current];
	for (let j = 0; j < neighbours.length; j++) {
		if (j != current && visited[j] == false) {
			let newDistance = distance[current] + neighbours[j];
			let oldDistance = distance[j];
			if (newDistance < oldDistance) {
				distance[j] = newDistance;
			}
		}
	}

	// 3 mark this node as visited
	visited[current] = true;
}

console.log(distance);