Graph Breadth First Search Depth First Search Shortest Path Minimum Spanning Tree
Proficient Level

Implement the networkDelayTimeCost method that returns the time needed for a signal to reach all nodes.

You are given a directed weighted graph as edges [from, to, time], the number of nodes, and a source node. Nodes are numbered from 1 to nodes.

Return the minimum time required for the signal to reach every node. If any node cannot be reached, return -1.

Example 1
Input:
nodes (int) = 4
edges (int[][]) = [[2,1,1],[2,3,1],[3,4,1]]
size (int) = 3
source (int) = 2
Return:
(int) 2
Example 2
Input:
nodes (int) = 2
edges (int[][]) = [[1,2,1]]
size (int) = 1
source (int) = 1
Return:
(int) 1
Example 3
Input:
nodes (int) = 2
edges (int[][]) = [[1,2,1]]
size (int) = 1
source (int) = 2
Return:
(int) -1

This is a shortest path problem from one source to all nodes.

Build an adjacency list and run Dijkstra's algorithm using a min heap. Each time the nearest unprocessed node is selected, relax its outgoing edges. After processing, the answer is the largest shortest distance among all nodes.

If any node still has infinite distance, not every node can receive the signal.

Pseudocode:

function networkDelayTimeCost(nodes, edges, size, source):
    build graph from edges
    distance = array filled with infinity
    distance[source] = 0
    heap = min heap with [0, source]
    while heap is not empty:
        [time, node] = remove minimum
        if time > distance[node]:
            continue
        for each [next, weight] in graph[node]:
            if time + weight < distance[next]:
                distance[next] = time + weight
                push [distance[next], next] into heap
    answer = maximum distance from 1 to nodes
    if answer is infinity:
        return -1
    return answer
Run your code to see the result.