All paths in a directed acyclic graph
All paths in a directed acyclic graph from a given source node to a given destination node can be found using Depth-First-Search traversal.
- Start from the source node and use DFS to reach the destination while storing the nodes along the path. Once the destination node is found, the path is stored.
Note
While finding all the paths, the DFS traversal techinique used here does not mark the nodes as visited while searching for the destination as a node in between can be revisited if it is present in a different path.
Algorithm Find_All_Paths (Graph g) 1.  Push the source node ‘src’ in the path. 2.  DFS (src, dest, g)
DFS (Source src, Destination dest, Graph g)
1.  If (src == dest) then
2.      A path has been found. Push the path in the list of all_the_paths.
3.  Else
4.    For every adjacent node ‘adj_node’ that is adjacent to src do
5.        Push ‘adj_node’ in the path.
6.        DFS (adj_node, dest, g)
7.        Pop ‘adj_node’ from the path. This is essentially a backtracing mechanism to find a different path from the source (‘src’) node.
Consider the below graph G2. The DFS traversal starts from the source 0 before the destination 3 is found. During the traversal, nodes 1 and 2 are visited before the desitnation 3 is reached. Since no nodes are marked visited, a different path is found that may pass through nodes 1 or 2 before reaching the desination 3.
Thus the DFS finds out the below paths..
[ 0 -> 1 -> 2 -> 3 ], path found.
Popout node 3 & 2. Next node ‘3’ adjacent to node 1 is visited.
[ 0 -> 1 -> 3 ], path found.
Popout node 3 & 1. Next node ‘2’ adjacent to node 0 is visited.
[ 0 -> 2 -> 3 ], path found.
Example
Implementation of finding all paths in a graph.
import copy
class Graph :
def __init__ (self):
self.allpaths = []
def FindAllPaths (self, graph, src, dst):
# Clear previously stored paths
path = []
path.append(src)
print("Source : " + str(src) + " Destination : " + str(dst))
# Use depth first search (with backtracking) to find all the paths in the graph
self.DFS (graph, src, dst, path)
# Print all paths
self.Print ()
def Print (self):
# print (self.allpaths)
for path in self.allpaths:
print("Path : " + str(path))
self.allpaths.clear()
# This function uses DFS at its core to find all the paths in a graph
def DFS (self, graph, src, dst, path):
if (src == dst):
self.allpaths.append(copy.deepcopy(path))
else:
for adjnode in graph[src]:
path.append(adjnode)
self.DFS (graph, adjnode, dst, path)
path.pop()
def main():
g1 = { 0 : [1, 2], 1 : [3], 2 : [3], 3 :[] } # 0 -> (1,2); 1 -> (3); 2 -> (3); 3 -> (None)
# 2 ---> 3
# ^ ^
# | |
# 0 ---> 1
#
g2 = { 0 : [1, 2], 1 : [2, 3], 2 : [3], 3 : [] } # 0 -> (1,2); 1 -> (2,3); 2 -> (3); 3 -> (None)
g3 = { 0 : [4, 3, 1], 1 : [3, 2, 4], 2 : [3], 3 : [4], 4 : [] }
g = Graph()
print("All paths in graph G1")
g.FindAllPaths(g1, 0, 3)
print("\nAll paths in graph G2")
g.FindAllPaths(g2, 0, 3)
print( "\nAll paths in graph G3")
g.FindAllPaths(g3, 0, 4)
if __name__ == "__main__":
main()
Output
All paths in graph G1
Source : 0 Destination : 3
Path : [0, 1, 3]
Path : [0, 2, 3]
All paths in graph G2
Source : 0 Destination : 3
Path : [0, 1, 2, 3]
Path : [0, 1, 3]
Path : [0, 2, 3]
All paths in graph G3
Source : 0 Destination : 4
Path : [0, 4]
Path : [0, 3, 4]
Path : [0, 1, 3, 4]
Path : [0, 1, 2, 3, 4]
Path : [0, 1, 4]
#include<iostream>
#include<vector>
using namespace std;
class Graph {
private :
vector<vector<int>> allpaths;
public:
void FindAllPaths (vector<vector<int>>& graph, int src, int dst) {
// Clear previously stored paths if any
allpaths.clear();
vector<int> path;
// As the path begins with source, push the source node into the path
path.push_back(src);
cout << "Source : " << src << " Destination : " << dst << endl;
DFS (graph, src, dst, path);
// Print all paths in the graph
Print ();
}
void Print() {
// Print all the paths
for (const auto& path : allpaths) {
cout << "Path : ";
for (const auto& node : path)
cout << node << " ";
cout << endl;
}
}
void DFS (vector<vector<int>>& graph, int src, int dst, vector<int>& path) {
if (src == dst) {
allpaths.push_back(path);
} else {
for (const auto& adjnode : graph[src]) {
path.push_back(adjnode);
DFS (graph, adjnode, dst, path);
path.pop_back();
}
}
}
};
int main() {
vector<vector<int>> g1 = {{1,2}, {3}, {3}, {}}; // 0 -> (1,2); 1 -> (3); 2 -> (3); 3 -> (None)
/* 2 ---> 3
^ ^
| |
0 ---> 1
*/
vector<vector<int>> g2 = {{1,2}, {2,3}, {3}, {}}; // 0 -> (1,2); 1 -> (2,3); 2 -> (3); 3 -> (None)
vector<vector<int>> g3 = {{4,3,1}, {3,2,4}, {3}, {4}, {}};
Graph g;
vector<vector<int>> allpaths;
cout << "All paths in graph G1" << endl;
g.FindAllPaths(g1, 0, 3);
cout << "\nAll paths in graph G2" << endl;
g.FindAllPaths(g2, 0, 3);
cout << "\nAll paths in graph G3" << endl;
g.FindAllPaths(g3, 0, 4);
return 0;
}
Output
All paths in graph G1
Source : 0 Destination : 3
Path : 0 1 3
Path : 0 2 3
All paths in graph G2
Source : 0 Destination : 3
Path : 0 1 2 3
Path : 0 1 3
Path : 0 2 3
All paths in graph G3
Source : 0 Destination : 4
Path : 0 4
Path : 0 3 4
Path : 0 1 3 4
Path : 0 1 2 3 4
Path : 0 1 4
import java.util.Arrays;
import java.util.ArrayList;
import java.util.List;
class Graph {
private List<Integer> path;
public void FindAllPaths (List<List<Integer>> graph, int src, int dst) {
// Clear previously stored paths
path = new ArrayList<Integer>();
path.clear();
System.out.print("Source : " + src + " Destination : " + dst);
path.add(src);
DFS (graph, src, dst, path);
}
public void DFS (List<List<Integer>> graph, int src , int dst, List<Integer> path) {
if (src == dst) {
System.out.print("\nPath : " );
for (Integer node : path)
System.out.print(node + " ");
} else {
for (Integer adjnode : graph.get(src)) {
path.add(adjnode);
DFS (graph, adjnode, dst, path);
path.remove(path.size()-1);
}
}
}
public static void ClearConnections(List<Integer> node1, List<Integer> node2, List<Integer> node3,
List<Integer> node4, List<Integer> node5) {
node1.clear();
node2.clear();
node3.clear();
node4.clear();
node5.clear();
}
public static void main (String[] args) {
Graph obj = new Graph();
List<Integer> from_node_0, from_node_1, from_node_2, from_node_3, from_node_4;
from_node_0 = new ArrayList<Integer>();
from_node_1 = new ArrayList<Integer>();
from_node_2 = new ArrayList<Integer>();
from_node_3 = new ArrayList<Integer>();
from_node_4 = new ArrayList<Integer>();
List<List<Integer>> graph1 = new ArrayList<List<Integer>>();
// Graph 1
/* 2 ---> 3
^ ^
| |
0 ---> 1 */
// {{1,2}, {3}, {3}, {}}; // 0 -> (1,2); 1 -> (3); 2 -> (3); 3 -> (None)
from_node_0.add(1);
from_node_0.add(2);
from_node_1.add(3);
from_node_2.add(3);
graph1.add(from_node_0);
graph1.add(from_node_1);
graph1.add(from_node_2);
graph1.add(from_node_3);
System.out.println("\n\nAll paths in graph G1");
obj.FindAllPaths (graph1, 0, 3);
// Graph 2
// {{1,2}, {2,3}, {3}, {}}; // 0 -> (1,2); 1 -> (2,3); 2 -> (3); 3 -> (None)
ClearConnections(from_node_0, from_node_1, from_node_2, from_node_3, from_node_4);
from_node_0.add(1);
from_node_0.add(2);
from_node_1.add(2);
from_node_1.add(3);
from_node_2.add(3);
List<List<Integer>> graph2 = new ArrayList<List<Integer>>();
graph2.add(from_node_0);
graph2.add(from_node_1);
graph2.add(from_node_2);
graph2.add(from_node_3);
System.out.println("\n\nAll paths in graph G2");
obj.FindAllPaths (graph2, 0 , 3);
// Graph 3
// {{4, 3, 1}, {3, 2, 4}, {3}, {4}}; // 0 -> (4, 3, 1); 1 -> (3, 2, 4); 2 -> (3); 3 -> (4)
ClearConnections(from_node_0, from_node_1, from_node_2, from_node_3, from_node_4);
from_node_0.add(4);
from_node_0.add(3);
from_node_0.add(1);
from_node_1.add(3);
from_node_1.add(2);
from_node_1.add(4);
from_node_2.add(3);
from_node_3.add(4);
List<List<Integer>> graph3 = new ArrayList<List<Integer>>();
graph3.add(from_node_0);
graph3.add(from_node_1);
graph3.add(from_node_2);
graph3.add(from_node_3);
graph3.add(from_node_4);
System.out.println("\n\nAll paths in graph G3");
obj.FindAllPaths (graph3, 0, 4);
}
}
Output
All paths in graph G1
Source : 0 Destination : 3
Path : 0 1 3
Path : 0 2 3
All paths in graph G2
Source : 0 Destination : 3
Path : 0 1 2 3
Path : 0 1 3
Path : 0 2 3
All paths in graph G3
Source : 0 Destination : 4
Path : 0 4
Path : 0 3 4
Path : 0 1 3 4
Path : 0 1 2 3 4
Path : 0 1 4