#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/graph-theory/dijkstra-s-algorithm/network-delay-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░███████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/graph-theory/dijkstra-s-algorithm/network-delay-implementation

Repovive

LeetCode 743 Network Delay Time - Implementation - Dijkstra's Algorithm | Graph Theory | Repovive

Repovive.

Graph Theory37 sections · 1633 units81h total

Open in Course

LeetCode 743 Network Delay Time - Implementation

Code solution

Here is the solution:

function networkDelayTime(times, n, k):
    adj = array of n + 1 empty lists
    for (u, v, w) in times:
        adj[u].append((v, w))

    dist = array of size n + 1, all infinity
    dist[k] = 0
    pq = min-heap with (0, k)

    while pq is not empty:
        (d, u) = pq.pop()
        if d > dist[u]:
            continue
        for (v, w) in adj[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                pq.push((dist[v], v))

    maxTime = 0
    for i from 1 to n:
        if dist[i] == infinity:
            return -1
        maxTime = max(maxTime, dist[i])
    return maxTime

This runs in $O((V + E) \log V)$ time and uses $O(V)$ space.