LEARNING JOURNAL

THE PROBLEM

This is the breadth-first search approach to solve this problem. It is much faster than the depth-first search approach that I've discussed (beats 83.18% of users with TypeScript). Well, who am I kidding? That percentage is kind of meaningless since it can vary (a lot) from one submission to another of the same code. But if the dfs approach only beats somewhere around 9.7% of users, it must mean something, right?

So, in this approach, I use an array of nodes called nextNodes to keep track of which nodes I need to process in the next round. At first, it only contains the source node (k) because on the next round which is also the first round, we need to examine the source node first. Then, we enter the while loop until there is not any next nodes to process (nextNodes.length === 0).

At each round of the while loop, we pick the nodes from nextNodes, one by one. For each of them, we get the edges array from the adjancy list (well, I forgot to mention, we need to build the adjency list adjList first which each key is the node and value is an array of pair in which the first value is the target node and the second value is the weight to the edge that leads to the target node.) For each edge, we check if we add that edge to our graph, does it create another path coming from the source node to the target node that is shorter than the current distance from source node to the target node. If it is, update the min value.

Then, we iterate through the min value array to find the maximum value, and return. If any of the element from the min value array still hasn't been updated yet and still kept the Infinity value, it means we can't reach all of the nodes from the source node. In that case, we return -1.

Revised by ChatGPT

This solution employs the breadth-first search (BFS) approach, which is significantly faster than the depth-first search (DFS) approach previously discussed. While the performance percentage (beating 83.18% of TypeScript users) can vary between submissions, a comparison with the DFS approach (which beats around 9.7% of users) indicates a notable improvement in efficiency.

Solution Overview:

• Adjacency List (adjList): First, construct an adjacency list where each key represents a node, and its value is an array of pairs. Each pair consists of a target node and the weight of the edge leading to that target node.
• Distance Array (minTimes): Initialize an array to keep track of the minimum time required to reach each node from the source node (k). Set the distance to the source node as 0 and all other distances to Infinity.
• Node Queue (nextNodes): Start with a queue containing the source node. In each iteration, process the nodes in this queue to explore their adjacent nodes.

BFS Algorithm:

1. While there are nodes in the queue: a. Create a temporary array to hold the nodes to be processed in the next round. b. For each node in the queue, iterate through its edges in the adjacency list. c. For each edge, if the current distance to the target node can be reduced by taking this edge, update the distance and add the target node to the temporary array.
2. Update the queue with the nodes from the temporary array.

Result Computation:

• Iterate through the minTimes array to find the maximum time required to reach a node from the source.
• If any node is still unreachable (distance is Infinity), return -1, indicating that not all nodes can be reached from the source.
• Othewise, return the maximum time.

This BFS approach ensures that we explore nodes level by level, updating the shortest paths to each node as we go, resulting in an efficient solution to the network delay time problem.