Network Delay Time

shriyanshi24jindal

Mar 30th, 2026

125

Never

Not a member of GistPad yet? Sign Up, it unlocks many cool features!

Java 13.44 KB | None | 0 0

copy raw download clone embed print report

class Pair
{
int vertex;
int weight;
Pair(int vertex, int weight)
{
this.vertex = vertex;
this.weight = weight;
}
}
class Solution {
/**
If you see: "shortest time / delay / distance", weights present, no DAG guarantee
then Instantly think: Dijkstra
Idea: give me the node with the smallest distance first using dijkastra algorithm
*/
public int networkDelayTime(int[][] times, int n, int k) {
// Step-1 Create an adjacency list where each node has {vertex, weight}
ArrayList<ArrayList<Pair>> adj = new ArrayList<>();
for(int i=0; i<=n; i++)
{
adj.add(new ArrayList<Pair>());
}
for(int[] edge : times)
{
int u = edge[0];
int v = edge[1];
int w = edge[2];
adj.get(u).add(new Pair(v,w));
}
// Step-2 Create a distance array
int[] distance = new int[n+1];
Arrays.fill(distance, Integer.MAX_VALUE);
distance[k] = 0;
// Step-3 Store the nodes into MIN-HEAP accoriding to node's weight to distances
PriorityQueue<Pair> pq = new PriorityQueue<>(
(a,b) -> Integer.compare(a.weight, b.weight)
);
pq.offer(new Pair(k, 0));
// Step-4 Relax the edges
while(!pq.isEmpty())
{
Pair pair = pq.poll();
int currentNode = pair.vertex;
for(Pair neighbour : adj.get(currentNode))
{
int vertex = neighbour.vertex;
int weight = neighbour.weight;
if(distance[vertex] > distance[currentNode] + weight)
{
distance[vertex] = distance[currentNode] + weight;
pq.offer(new Pair(vertex, distance[vertex]));
}
}
}
// Step-5 If any node is unreachable then return -1
// the distance array contains the shortest path from k to every node.
int maxDistance = 0;
for(int i=1; i<=n; i++)
{
if(distance[i] == Integer.MAX_VALUE)
return -1;
// maximum of all shortest distances, because that’s when the signal has reached everyone.
maxDistance = Math.max(maxDistance, distance[i]);
}
return maxDistance;
}
}

RAW Paste Data Copied

class Pair
{
    int vertex;
    int weight;
    Pair(int vertex, int weight)
    {
        this.vertex = vertex;
        this.weight = weight;
    }
}

class Solution {
    /**
    If you see: "shortest time / delay / distance", weights present, no DAG guarantee
    then Instantly think: Dijkstra
    Idea: give me the node with the smallest distance first using dijkastra algorithm
    */
    public int networkDelayTime(int[][] times, int n, int k) {
        
        // Step-1 Create an adjacency list where each node has {vertex, weight}
        ArrayList<ArrayList<Pair>> adj = new ArrayList<>();
        for(int i=0; i<=n; i++)
        {
            adj.add(new ArrayList<Pair>());
        }

for(int[] edge : times)
        {
            int u = edge[0];
            int v = edge[1];
            int w = edge[2];

adj.get(u).add(new Pair(v,w));
        }

// Step-2 Create a distance array
        int[] distance = new int[n+1];
        Arrays.fill(distance, Integer.MAX_VALUE);
        distance[k] = 0;

// Step-3 Store the nodes into MIN-HEAP accoriding to node's weight to distances
        PriorityQueue<Pair> pq = new PriorityQueue<>(
            (a,b) -> Integer.compare(a.weight, b.weight)
        );
        pq.offer(new Pair(k, 0));

// Step-4 Relax the edges
        while(!pq.isEmpty())
        {
            Pair pair = pq.poll();
            int currentNode = pair.vertex;

for(Pair neighbour : adj.get(currentNode))
            {
                int vertex = neighbour.vertex;
                int weight = neighbour.weight;

if(distance[vertex] > distance[currentNode] + weight)
                {
                    distance[vertex] = distance[currentNode] + weight;
                    pq.offer(new Pair(vertex, distance[vertex]));
                }
            }
        }

// Step-5 If any node is unreachable then return -1
        // the distance array contains the shortest path from k to every node.
        int maxDistance = 0;
        for(int i=1; i<=n; i++) 
        {
            if(distance[i] == Integer.MAX_VALUE)
                return -1;
            // maximum of all shortest distances, because that’s when the signal has reached everyone.
            maxDistance = Math.max(maxDistance, distance[i]);
        }
        return maxDistance;
    }
}