Railway Network Delay Optimizer

Published at05 Jan 2026

Graph Dijkstra Hard 22 views

Like24

You are given a network of n nodes labeled from 1 to n. There are `times` directed edges where times[i] = [u, v, w] means a signal travels from node u to node v in w time units.

The signal starts at a given node k. It propagates outward through the network along the directed edges. Your task is to compute the minimum time it takes for the signal to reach all n nodes. Return the time at which the last node receives the signal.

If the signal cannot reach every node (some node is unreachable from k), return -1.

For example, with times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, and k = 2, the signal reaches node 1 in 1, node 3 in 1, and node 4 in 2 units. The last node (4) receives it at time 2, so the answer is 2. If a node is unreachable, like times = [[1,2,1]] with n=2 and k=2, node 1 cannot be reached, so the answer is -1.

This is the classic single-source shortest path problem on a weighted directed graph, best solved with Dijkstra's algorithm using a priority queue. Because edge weights are non-negative, Dijkstra guarantees the first time a node is finalized its distance is minimal.

Edge cases include an empty graph (if k is the only node, the answer is 0), a start node that is also the only reachable node (return 0), and graphs where some nodes form an unreachable component (return -1).

Example Input & Output

Example 1

Input

times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2

Output

Explanation

Signal reaches node 4 last at time 2.

Example 2

Input

times = [[1,2,1]], n = 2, k = 2

Output

-1

Explanation

Node 1 is unreachable from node 2.

Example 3

Input

times = [[1,2,1],[2,3,2],[1,3,4]], n = 3, k = 1

Output

Explanation

Best path 1 -> 2 -> 3 arrives at time 3.

Algorithm Flow

Recommendation Algorithm Flow for Railway Network Delay Optimizer

Solution Approach

This is the classic single-source shortest path problem on a weighted directed graph, best solved with Dijkstra's algorithm. The signal starts at node k and propagates along directed edges, and we want the time when the last node receives it — in other words, the maximum shortest distance from k to any other node.

Because all edge weights are non-negative, Dijkstra's algorithm is correct and efficient. It visits nodes in order of increasing distance, and the first time a node is finalized its distance is guaranteed to be minimal. If any node is unreachable, we return -1.

Here is the implementation:

function network_delay_time(times, n, k) {
    const adj = Array.from({ length: n + 1 }, () => []);
    for (const [u, v, w] of times) {
        adj[u].push([v, w]);
    }
    const dist = new Array(n + 1).fill(Infinity);
    dist[k] = 0;
    const pq = [[0, k]];
    while (pq.length > 0) {
        pq.sort((a, b) => a[0] - b[0]);
        const [d, u] = pq.shift();
        if (d > dist[u]) continue;
        for (const [v, w] of adj[u]) {
            const nd = d + w;
            if (nd < dist[v]) {
                dist[v] = nd;
                pq.push([nd, v]);
            }
        }
    }
    let maxDist = 0;
    for (let i = 1; i <= n; i++) {
        if (dist[i] === Infinity) return -1;
        maxDist = Math.max(maxDist, dist[i]);
    }
    return maxDist;
}

We build a directed adjacency list from the times edges, then initialize the distance to the start as 0 and everything else as infinity. A priority queue (simulated with a sorted array here) always extracts the closest unprocessed node. When a shorter path to a neighbor is found, we relax it and push it onto the queue.

After the search, we scan all nodes. If any distance is still infinity, the node is unreachable and we return -1. Otherwise the answer is the maximum distance, which is the time the last node receives the signal.

Let us verify with times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2. Node 1 is reached in 1, node 3 in 1, and node 4 via 3 in 2. The maximum is 2, which is the answer. For times = [[1,2,1]], n = 2, k = 2, node 1 is unreachable, so we return -1.

The time complexity is O((n + e) log n) with a real priority queue, and the space complexity is O(n + e).

Best Answers
These are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.

java

import java.util.*;
class Solution {
    public int optimize_railway_delay(int[][] times, int n, int k) {
        List<int[]>[] adj = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) adj[i] = new ArrayList<>();
        for (int[] t : times) adj[t[0]].add(new int[]{t[1], t[2]});
        int[] dist = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[k] = 0;
        boolean[] visited = new boolean[n + 1];
        for (int it = 0; it < n; it++) {
            int u = -1, best = Integer.MAX_VALUE;
            for (int v = 1; v <= n; v++) {
                if (!visited[v] && dist[v] < best) { best = dist[v]; u = v; }
            }
            if (u == -1) break;
            visited[u] = true;
            for (int[] e : adj[u]) {
                int v = e[0], w = e[1];
                if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;
            }
        }
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            if (dist[i] == Integer.MAX_VALUE) return -1;
            ans = Math.max(ans, dist[i]);
        }
        return ans;
    }
}

javascript

function optimize_railway_delay(times, n, k) {
    const adj = Array.from({ length: n + 1 }, () => []);
    for (const [u, v, w] of times) adj[u].push([v, w]);
    const dist = new Array(n + 1).fill(Infinity);
    dist[k] = 0;
    const pq = [[0, k]];
    while (pq.length > 0) {
        pq.sort((a, b) => a[0] - b[0]);
        const [d, u] = pq.shift();
        if (d > dist[u]) continue;
        for (const [v, w] of adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push([dist[v], v]);
            }
        }
    }
    let maxDist = 0;
    for (let i = 1; i <= n; i++) {
        if (dist[i] === Infinity) return -1;
        maxDist = Math.max(maxDist, dist[i]);
    }
    return maxDist;
}

php

<?php

function optimize_railway_delay($times, $n, $k) {
    $adj = array_fill(1, $n, []);
    foreach ($times as $t) $adj[$t[0]][] = [$t[1], $t[2]];
    $dist = array_fill(1, $n, INF);
    $dist[$k] = 0;
    $pq = [[0, $k]];
    while (!empty($pq)) {
        usort($pq, function($a, $b) { return $a[0] - $b[0]; });
        $u_data = array_shift($pq);
        $d = $u_data[0]; $u = $u_data[1];
        if ($d > $dist[$u]) continue;
        if (!isset($adj[$u])) continue;
        foreach ($adj[$u] as $v_data) {
            $v = $v_data[0]; $w = $v_data[1];
            if ($dist[$u] + $w < $dist[$v]) {
                $dist[$v] = $dist[$u] + $w;
                $pq[] = [$dist[$v], $v];
            }
        }
    }
    $maxDist = 0;
    for ($i = 1; $i <= $n; $i++) {
        if ($dist[$i] == INF) return -1;
        $maxDist = max($maxDist, $dist[$i]);
    }
    return $maxDist;
}

python

import heapq
def optimize_railway_delay(times, n, k):
    adj = {i: [] for i in range(1, n + 1)}
    for u, v, w in times:
        adj[u].append((v, w))
    pq = [(0, k)]
    visited = {}
    while pq:
        d, u = heapq.heappop(pq)
        if u in visited: continue
        visited[u] = d
        for v, w in adj[u]:
            if v not in visited:
                heapq.heappush(pq, (d + w, v))
    if len(visited) < n: return -1
    return max(visited.values())

rust

use std::collections::HashMap;
pub fn optimize_railway_delay(times: Vec<Vec<i32>>, n: i32, k: i32) -> i32 {
    let mut adj: HashMap<i32, Vec<(i32, i32)>> = HashMap::new();
    for t in &times {
        adj.entry(t[0]).or_insert(Vec::new()).push((t[1], t[2]));
    }
    let mut dist = vec![std::i32::MAX; (n + 1) as usize];
    dist[k as usize] = 0;
    let mut visited = vec![false; (n + 1) as usize];
    for _ in 0..n {
        let mut u = -1;
        let mut best = std::i32::MAX;
        for v in 1..=n {
            if !visited[v as usize] && dist[v as usize] < best {
                best = dist[v as usize];
                u = v;
            }
        }
        if u == -1 { break; }
        visited[u as usize] = true;
        if let Some(neigh) = adj.get(&u) {
            for &(v, w) in neigh {
                let nd = dist[u as usize].saturating_add(w);
                if nd < dist[v as usize] {
                    dist[v as usize] = nd;
                }
            }
        }
    }
    let mut ans = 0;
    for i in 1..=n {
        if dist[i as usize] == std::i32::MAX { return -1; }
        if dist[i as usize] > ans { ans = dist[i as usize]; }
    }
    ans
}

typescript

function optimize_railway_delay(times: number[][], n: number, k: number): number {
    var adj: number[][][] = [];
    for (var i = 0; i <= n; i++) adj[i] = [];
    for (var j = 0; j < times.length; j++) {
        var u = times[j][0], v = times[j][1], w = times[j][2];
        adj[u].push([v, w]);
    }
    var dist: number[] = [];
    for (var i = 0; i <= n; i++) dist[i] = Infinity;
    dist[k] = 0;
    var pq: number[][] = [[0, k]];
    while (pq.length) {
        pq.sort(function(a, b) { return a[0] - b[0]; });
        var cur = pq.shift();
        var d = cur[0], u = cur[1];
        if (d > dist[u]) continue;
        for (var e = 0; e < adj[u].length; e++) {
            var v = adj[u][e][0], w = adj[u][e][1];
            if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; pq.push([dist[v], v]); }
        }
    }
    var ans = 0;
    for (var i = 1; i <= n; i++) { if (dist[i] === Infinity) return -1; if (dist[i] > ans) ans = dist[i]; }
    return ans;
}

Related Graph Challenges

Comments (0)

Join the Discussion

Share your thoughts, ask questions, or help others with this Challenge.

Railway Network Delay Optimizer

Example Input & Output

Algorithm Flow

Solution Approach

Best AnswersThese are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.

Solutions Coming Soon

Related Graph Challenges

Interstate Rescue Network Audit

Wildlife Bridge Network Scan

Metro Transfer Capacity Map

City Signal Span

Memory Rune Sequencer

Shortest Path in Weighted Graph

Comments (0)

Join the Discussion

Best Answers
These are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.