Categories
Algorithms Javascript

Dijkstra Algorithm in JS

const networkDelayTime = function (times, n, src) {
	const adjacencyList = new Map();

	for (let [start, end, cost] of times) {
		adjacencyList.set(
			start,
			(adjacencyList.get(start) || []).concat([[end, cost]])
		);
	}
	const queue = new MinPriorityQueue({
		compare: (a, b) => a[0] > b[0],
	});
	queue.enqueue([0, src]); // cost, start
	const visited = new Map();
	while (queue.size()) {
		const [cost, node] = queue.dequeue();
		if (visited.has(node)) continue;
		visited.set(node, cost);
		// if (city === dst) return cost;
		if (!adjacencyList.has(node)) continue;
		for (const [nextNode, nextCost] of adjacencyList.get(node)) {
			if (visited.has(nextNode) || visited.get(nextNode) >= cost)
				continue;
			queue.enqueue([cost + nextCost, nextNode]);
		}
	}
	return visited.size == n ? Math.max(...visited.values()) : -1;
};

T: O(N+ElogN)

S: O(N+E)

Leave a Reply

Your email address will not be published. Required fields are marked *