Here’s a famous problem:

Given a Directed Acyclic Graph of N vertices from 0 to N-1 and a 2D Integer array(or vector) edges[ ][ ] of length M, where there is a directed edge from edge[i][0] to edge[i][1] with a distance of edge[i][2] for all i.

Find the shortest path from src(0) vertex to all the vertices and if it is impossible to reach any vertex, then return -1 for that vertex.

Here’s how I solve using dfs. I take each of the node and pass through the dfs function and keep updating the the target Node distance in dis array. And I see this works fine for a couple of test cases.

const edge = [[0,1,2],[0,4,1],[4,5,4],[4,2,2],[1,2,3],[2,3,6],[5,3,1]];
const N = 6, M = 7;

let graph = {}, dis = [];

for(var i=0; i<N; i++){
    graph[i] = [];
    dis[i] = Infinity; // Intitalize each of the node's distance to Infinity.
}

// Create adjacency list

for(let vertex of edge){
    var [node, child, distance] = vertex;
    graph[node].push([child, distance]);
}

const dfs = function(graph, node, targetNode){
    if(node === targetNode) return 0;
   
   let minDistance = Infinity;
    
    for(let k of graph[node]){
        const [el, distance] = k;
        minDistance = Math.min(minDistance, distance+dfs(graph, el, targetNode))
    }
    
    return minDistance;
}

for(var i=0; i<N; i++){
    dis[i] = dfs(graph, 0, i); //call the dfs with each of the node as target and 0 being the source
}

console.log(dis);

Now the solutions that I see almost always use topological sort and I’m pretty sure, there could be some good reason for that. So my question is, is that so or the above program is just fine. I’m unable to test this for all test cases because the platform I refer to for this problem only has java and c++ support.