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 .
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]]