# 10. Dijkstra algorithm

[dijkstra-algorithm-directed-shortest-path](https://algorithm.prettylog.com/overview/3.-how-to-construct-algorithm-paradigm/shortest-path/dijkstra-algorithm-directed-shortest-path "mention")

743\. Network Delay TimeMedium6.4K334Companies

You are given a network of `n` nodes, labeled from `1` to `n`. You are also given `times`, a list of travel times as directed edges `times[i] = (ui, vi, wi)`, where `ui` is the source node, `vi` is the target node, and `wi` is the time it takes for a signal to travel from source to target.

We will send a signal from a given node `k`. Return *the **minimum** time it takes for all the* `n` *nodes to receive the signal*. If it is impossible for all the `n` nodes to receive the signal, return `-1`.

**Example 1:**

![](https://assets.leetcode.com/uploads/2019/05/23/931_example_1.png)

<pre><code><strong>Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
</strong><strong>Output: 2
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: times = [[1,2,1]], n = 2, k = 1
</strong><strong>Output: 1
</strong></code></pre>

**Example 3:**

<pre><code><strong>Input: times = [[1,2,1]], n = 2, k = 2
</strong><strong>Output: -1
</strong></code></pre>

**Constraints:**

* `1 <= k <= n <= 100`
* `1 <= times.length <= 6000`
* `times[i].length == 3`
* `1 <= ui, vi <= n`
* `ui != vi`
* `0 <= wi <= 100`
* All the pairs `(ui, vi)` are **unique**. (i.e., no multiple edges.)

{% embed url="<https://leetcode.com/problems/network-delay-time/description/>" %}

### with visited checking

> We do not need to visit a vertex already visited cuz visited vertex got a shortest path already from a start vertex

```jsx
/**
 * @param {number[][]} times
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
var networkDelayTime = function (times, n, k) {
    // create adjs

    // adjecent list
    const adjs = {};
    // minimum dist at vertex i
    const dist = [];
    // vertex where relaxation is done
    const visited = new Set();
    // track prev vertex connected to current i
    const ids = [];

    // initialize
    for (let i = 0; i <= n; i++) {
        adjs[i] = [];
        ids[i] = i;
        dist[i] = Infinity;
    }

    // create adjecent list
    for (const [u, v, w] of times) {
        adjs[u].push([v, w]);
    }

    // heap to track current vertex, no visited and minimum 
    const minHeap = new Heap([], (a, b) => a[1] <= b[1]);
    
    // insert start vertex with distance 0
    minHeap.insert([k, 0]);
    dist[k] = 0;

    while (minHeap.size > 0) {
        // console.log('before:: ', minHeap.heap);
        const [here, currentWeight] = minHeap.remove();

        // other than using visited arr, we can just filter visited vertex by doing this
        // property a -> b -> c, a -> c is shortest path then a->b, b -> c also shortest
        // if (dist[here] < currentWeight) continue;
        
        const adj = adjs[here];
        for (const [there, w] of adj) {
            if (visited.has(there)) 
                continue;
            
            // current min distance to vertex there from start
            const prev = dist[there];
            
            // dist[here] is equal to currentWeight if we do not put visited vertex again into the heap
            const next = dist[here] + w; 
            
            if (prev > next) {
                // change prev vertex
                ids[there] = here;
                // update minimum distance 
                dist[there] = next;

                minHeap.insert([there, next]);
            }
        }
        // console.log('after:: ', minHeap.heap);

        visited.add(here); 
    }

    let max = -Infinity;
    // vertex starts from 1
    for (let i = 1; i <= n; i++) {
        if (dist[i] === Infinity) return -1;
        max = Math.max(dist[i], max);
    }

    return max;
};

class Heap {
    constructor(arr, predicate = (a, b) => a <= b) {
        this.predicate = predicate;
        this.size = arr.length;
        this.heap = this.buildHeap(arr);
    }

    buildHeap(arr) {
        let currentIndex = Math.floor((arr.length - 1 - 1) / 2);
        while (currentIndex >= 0) {
            this.siftDown(arr, currentIndex, arr.length - 1);
            currentIndex--;
        }

        return arr;
    }

    insert(v) {
        this.heap.push(v);
        this.size++;

        this.siftUp(this.heap, this.heap.length - 1);

    }

    remove(v) {
        this.swap(this.heap, 0, this.heap.length - 1);
        const elementToRemove = this.heap.pop();
        this.size--;
        
        this.siftDown(this.heap, 0, this.heap.length - 1);
        return elementToRemove;
    }

    siftUp(heap, currentIndex) {
        let parentIndex = Math.floor((currentIndex - 1) / 2);
        while (parentIndex >= 0) {
            if (this.predicate(heap[parentIndex], heap[currentIndex])) {
                break;
            }

            this.swap(heap, parentIndex, currentIndex);
            currentIndex = parentIndex;
            parentIndex = Math.floor((currentIndex - 1) / 2);
        }
        return heap;
    }

    siftDown(heap, currentIndex, endIndex) {
        let left = currentIndex * 2 + 1;

        while (left <= endIndex) {
            let min = left;
            const right = currentIndex * 2 + 2;
            if (heap[right] !== undefined && this.predicate(heap[right], heap[min])) {
                min = right;
            }

            if (this.predicate(heap[currentIndex], heap[min])) break;
            this.swap(heap, currentIndex, min);
            currentIndex = min;
            left = currentIndex * 2 + 1;
        }

        return heap;
    }

    swap(arr, a, b) {
        [arr[b], arr[a]] = [arr[a], arr[b]];
    }

}
```

### without visited checking

[LeetCode - The World's Leading Online Programming Learning Platform](https://leetcode.com/problems/network-delay-time/submissions/972263661/)

```jsx
/**
 * @param {number[][]} times
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
var networkDelayTime = function (times, n, k) {
    // create adjs

    // adjecent list
    const adjs = {};
    // minimum dist at vertex i
    const dist = [];
    // track prev vertex connected to current i
    const ids = [];

    // initialize
    for (let i = 0; i <= n; i++) {
        adjs[i] = [];
        ids[i] = i;
        dist[i] = Infinity;
    }

    // create adjecent list
    for (const [u, v, w] of times) {
        adjs[u].push([v, w]);
    }

    // heap to track current vertex, no visited and minimum 
    const minHeap = new Heap([], (a, b) => a[1] <= b[1]);
    
    // insert start vertex with distance 0
    minHeap.insert([k, 0]);
    dist[k] = 0;

    while (minHeap.size > 0) {
        const [here, currentWeight] = minHeap.remove();

        // other than using visited arr, we can just filter visited vertex by doing this
        // property a -> b -> c, a -> c is shortest path then a->b, b -> c also shortest
        // if (dist[here] < currentWeight) continue;
        
        const adj = adjs[here];
        for (const [there, w] of adj) {
            
            // current min distance to vertex there from start
            const prev = dist[there];
            
            // dist[here] is equal to currentWeight if we do not put visited vertex again into the heap
            const next = dist[here] + w; 
            
            if (prev > next) {
                // change prev vertex
                ids[there] = here;
                // update minimum distance 
                dist[there] = next;

                minHeap.insert([there, next]);
            }
        }
    }

    let max = -Infinity;
    // vertex starts from 1
    for (let i = 1; i <= n; i++) {
        if (dist[i] === Infinity) return -1;
        max = Math.max(dist[i], max);
    }

    return max;
};

class Heap {
    constructor(arr, predicate = (a, b) => a <= b) {
        this.predicate = predicate;
        this.size = arr.length;
        this.heap = this.buildHeap(arr);
    }

    buildHeap(arr) {
        let currentIndex = Math.floor((arr.length - 1 - 1) / 2);
        while (currentIndex >= 0) {
            this.siftDown(arr, currentIndex, arr.length - 1);
            currentIndex--;
        }

        return arr;
    }

    insert(v) {
        this.heap.push(v);
        this.size++;

        this.siftUp(this.heap, this.heap.length - 1);

    }

    remove(v) {
        this.swap(this.heap, 0, this.heap.length - 1);
        const elementToRemove = this.heap.pop();
        this.size--;
        
        this.siftDown(this.heap, 0, this.heap.length - 1);
        return elementToRemove;
    }

    siftUp(heap, currentIndex) {
        let parentIndex = Math.floor((currentIndex - 1) / 2);
        while (parentIndex >= 0) {
            if (this.predicate(heap[parentIndex], heap[currentIndex])) {
                break;
            }

            this.swap(heap, parentIndex, currentIndex);
            currentIndex = parentIndex;
            parentIndex = Math.floor((currentIndex - 1) / 2);
        }
        return heap;
    }

    siftDown(heap, currentIndex, endIndex) {
        let left = currentIndex * 2 + 1;

        while (left <= endIndex) {
            let min = left;
            const right = currentIndex * 2 + 2;
            if (heap[right] !== undefined && this.predicate(heap[right], heap[min])) {
                min = right;
            }

            if (this.predicate(heap[currentIndex], heap[min])) break;
            this.swap(heap, currentIndex, min);
            currentIndex = min;
            left = currentIndex * 2 + 1;
        }

        return heap;
    }

    swap(arr, a, b) {
        [arr[b], arr[a]] = [arr[a], arr[b]];
    }

}
```

### without visited checking and adding filter condition

```jsx
while (minHeap.size > 0) {
        const [here, currentWeight] = minHeap.remove();

        // other than using visited arr, we can just filter visited vertex by doing this
        // property a -> b -> c, a -> c is shortest path then a->b, b -> c also shortest
        if (dist[here] < currentWeight) continue;
        
        const adj = adjs[here];
        for (const [there, w] of adj) {
            
            // current min distance to vertex there from start
            const prev = dist[there];
            
            // dist[here] is equal to currentWeight if we do not put visited vertex again into the heap
            const next = dist[here] + w; 
            
            if (prev > next) {
                // change prev vertex
                ids[there] = here;
                // update minimum distance 
                dist[there] = next;

                minHeap.insert([there, next]);
            }
        }
    }
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://algorithm.prettylog.com/algorithm-problems/daily-algorithms/10.-dijkstra-algorithm.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.