DEV Community

Minh Le
Minh Le

Posted on

743. Network Delay Time - Depth First Search Approach

function networkDelayTime(times: number[][], n: number, k: number): number {


   const adjList: Record<string, [number,number][]> = {};
   for(let i = 0; i < times.length; i++) {
       if(!adjList[String(times[i][0])]) {
           adjList[String(times[i][0])] = [[times[i][1], times[i][2]]];
       }
       else {
           adjList[String(times[i][0])].push([times[i][1], times[i][2]]);
       }
   }

    const curTimes = Array(n + 1).fill(Infinity);
    curTimes[k] = 0;

    dfs(adjList[String(k)], k);

    function dfs(edges:[number,number][]|undefined, curV:number) {
        if(edges === undefined) return;

        for(let i = 0; i < edges.length; i++) {
            const curE = edges[i];

            if(curE[1] + curTimes[curV] < curTimes[curE[0]]){
                curTimes[curE[0]] = curE[1] + curTimes[curV];
                dfs(adjList[String(curE[0])], curE[0]);
            }



        }
    }

    let max = 0;

    for(let i = 1; i < curTimes.length; i++) {
        if(curTimes[i] === Infinity)
            return -1;

        if(max < curTimes[i]) {
            max = curTimes[i];
        }
    }

    return max;

};
Enter fullscreen mode Exit fullscreen mode

This problem is solved using a depth-first search (DFS) approach. Initially, I considered using a min-heap to select the smallest weight edge and then adding the target vertex to the graph. However, this method only yields the total length of the shortest-spanning tree, which is not the required solution for this problem.

In the DFS approach, the algorithm explores all possible paths originating from the source vertex. During each iteration, it updates the distance from the source to the current vertex with the minimum value found so far. For example, consider two paths from the source vertex s to vertex 3. If the first path takes 3 units of time to reach vertex 3, this value is recorded. Upon exploring the second path, if it takes only 2 units of time to reach vertex 3, the distance from s to 3 is updated to 2. Conversely, if the second path takes more than 3 units of time, no update is made, as a shorter path already exists.

The algorithm ensures that the shortest time to reach each vertex from the source is calculated, and the maximum of these times is returned as the final result. If any vertex is unreachable from the source, the function returns -1.

Image of Timescale

🚀 pgai Vectorizer: SQLAlchemy and LiteLLM Make Vector Search Simple

We built pgai Vectorizer to simplify embedding management for AI applications—without needing a separate database or complex infrastructure. Since launch, developers have created over 3,000 vectorizers on Timescale Cloud, with many more self-hosted.

Read full post →

Top comments (0)

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more

đź‘‹ Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay