CODEWITHSUNDEEP
javascriptalgorithmdata-structuresgraph-algorithmdirected-graph
Sumeet Kumar Yadav
Sumeet Kumar Yadav

Reputation: 13015

All possible path to reach particular node in directed graph

I have a directed graph where paths are stored in JSON array like. It is in the form of source and destination .

Var pathDirection =  [{"Source":2,"Destination":3},
{"Source":3,"Destination":4},
{"Source":5,"Destination":4},
{"Source":2,"Destination":5},
{"Source":4,"Destination":6}];

Using above it forms graph like below structure .

enter image description here

My problem is I don’t know the starting point and I have to find all possible path to reach 6 from any node

Like for above graph different path to reach 6 is

Output:

    [4 ->6]
    [3->4 ->6]
    [5->4 ->6]
    [2->5->4 ->6]
    [2->3->4 ->6]

I have tried to write below algo using backtracking which is working fine but looking for some best algo to find. Please suggest any other possible way to do same and how can i optimize below programe.

// BackTrack From End Node Destination 6

var getAllSource = function(destId){
    var sourceForsameDist = [];
    pathDirection.forEach(function(eachDirection){
      if(eachDirection.Destination == destId){
        sourceForsameDist.push(eachDirection.Source);
      }
  });
        return sourceForsameDist;
};

var diffPath = [];

var init = function(destination){
   var sourceId =  getAllSource(destination[destination.length - 1]);
    if(sourceId.length === 0){
      diffPath.push(destination);

    }
   for(var i=0;i<sourceId.length;i++){
     var copy  = destination.slice(0);
     copy.push(sourceId[i]);
     init(copy);
   }

};

init([6]);

console.log(diffPath);  // [[6,4,3,2],[6,4,5,2]]

Upvotes: 1

Views: 2054

Answers (1)

Bergi
Bergi

Reputation: 665546

I have tried to do using backtracking which is working fine but looking for some best algo to find.

I'd call it Depth-First-Search instead of backtracking, but yes the algorithm is fine.

However, I'd have some suggestions on the implementation:

  • make diffPath a local variable and return it from the init function
  • If you omit the if(sourceId.length === 0) condition then you will get the expected output, not only the the paths from the sources
  • instead of looping through the whole pathDirections in your getAllSource function, I'd use a lookup table that is filled before starting the traversal
  • rename init to something more meaningful

Upvotes: 1

Related Questions