Dijkstra - Greedy BFS

Single source shortest path Ref: https://www.youtube.com/watch?v=XB4MIexjvY0

• BFS won’t work for weightage edges
• Dijkstra is GREEDY BFS
  • Optimization | Minimization | Greedy
• “One step at a time” and Be Greedy
• BFS using MinHeap ⇒ Greedy BFS
• Relaxation (just like Bellman Ford)

dist[v] = min(dist[v], dist[u] + weight)

---

Network Delay time

https://neetcode.io/problems/network-delay-time/question Return the minimum time it takes for all of the n nodes to receive the signal from node k. If it is impossible for all the nodes to receive the signal, return -1 instead.

• Time complexity: O(Elog⁡V)
• Space complexity: O(V+E)

const { MinPriorityQueue } = require('@datastructures-js/priority-queue');
 
var networkDelayTime = function(times, n, k) {
    const adj = {};
    for (let i = 1; i <= n; i++) {
        adj[i] = [];
    }
 
    for (const [src, dst, weight] of times) {
        adj[src].push([dst, weight]);
    }
 
    const minHeap = new MinPriorityQueue((entry) => entry[0]);
    minHeap.enqueue([0, k]); // [time, node]
 
    const visited = new Set();
    let result = 0;
 
    while (!minHeap.isEmpty()) {
        const [w1, n1] = minHeap.dequeue();
 
        if (visited.has(n1)) continue;
 
        visited.add(n1);
        result = w1;
 
        for (const [n2, w2] of adj[n1]) {
            if (!visited.has(n2)) {
                minHeap.enqueue([w1 + w2, n2]);
            }
        }
    }
 
    return visited.size === n ? result : -1;
};