[Dijkstra] Network Delay Time

[sudosf]

Problem

Given a network of n nodes, times array of directed edges (u, v, w), and source k, return the minimum time for all nodes to receive the signal. Return -1 if impossible.

References

• LeetCode: https://leetcode.com/problems/network-delay-time/
• GFG: https://www.geeksforgeeks.org/problems/network-delay-time/1
• Sheet: https://www.risingbrain.org/sheet#graph (Dijkstra [Two Pointer] Move Zeroes #4)
• Parent: Pattern: Graph - Dijkstra Shortest Path #129

Difficulty

🟡 Medium

Companies

Amazon, Google, Goldman Sachs

Notes

Language: Java
Standard Dijkstra from source k. Answer is max of all shortest distances. If any node unreachable, return -1.