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;

};

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.