Learning Journal

3/7/2024

Network Delay Time - Depth First Search Approach

Tags: algorithms leetcode graph depth_first_search

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;

};


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;

};

THE PROBLEM

This is the depth-first search approach for this problem. At first, I thought it can be solved easily by using a min heap to pop the smallest weight edge then add the target vertex to the graph. However, it turns out that the algorithm only finds the total length of the shortest spanning tree, not the result for this problem.

So, this is the depth-first search for this problem. Basically, it traverses to the end of all possible paths coming from the source. During each iteration, it will update the distance between the source to the current vertex to the smallest value. For example, if there are 2 paths coming from the vertex s to the vertex 3, when traversing the first path, we discover that if going by that path to 3, we need 3 units of time. Then, after finishing the first path, we traverse the second path and found out that we need 2 units of time to go to 3 by that path, so, we update the distance from s to 3 to 2. Otherwise, if we need more than 3 units of time to go to 3 by path 2, we don't do anything and just return, because we know that there is another way that goes to 3 and any vertex after 3 that is shorter than the current path.

Revised by ChatGPT

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.