**Objective**: Given a graph, source vertex and destination vertex. Write an algorithm to count all possible paths between source and destination.

Condition: Graph does not contain any cycle.

This problem also known as “paths between two nodes”

**Example**:

**Approach**: Use Depth First Search

- Use DFS but we cannot use visited [] to keep track of visited vertices since we need to explore all the paths. visited [] is used avoid going into cycles during iteration. (That is why we have a condition in this problem that graph does not contain cycle)
- Start from the source vertex and make a recursive call to all it adjacent vertices.
- During recursive call, if reach the destination vertex, increment the result (no of paths).
- See the code for more understanding.

**Code**:

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

import java.util.LinkedList; | |

public class CountPaths { | |

static int paths =0; | |

static class Graph{ | |

int vertices; | |

LinkedList<Integer>[] adjList; | |

Graph(int vertices){ | |

this.vertices = vertices; | |

adjList = new LinkedList[vertices]; | |

for (int i = 0; i <vertices ; i++) { | |

adjList[i] = new LinkedList<>(); | |

} | |

} | |

public void addEgde(int source, int destination){ | |

adjList[source].addFirst(destination); | |

} | |

public void countPaths(int source, int destination){ | |

count(source, destination); | |

System.out.println("No of paths between source: " + source | |

+ " and destination: " + destination + " are:" + paths); | |

} | |

public void count(int start, int destination){ | |

if(start==destination) { | |

paths++; | |

}else { | |

for (int i = 0; i < adjList[start].size(); i++) { | |

int ajdacentVertex = adjList[start].get(i); | |

count(ajdacentVertex, destination); | |

} | |

} | |

} | |

} | |

public static void main(String[] args) { | |

int vertices = 6; | |

Graph graph = new Graph(vertices); | |

graph.addEgde(0, 1); | |

graph.addEgde(0, 2); | |

graph.addEgde(1, 2); | |

graph.addEgde(1, 3); | |

graph.addEgde(3, 4); | |

graph.addEgde(2, 3); | |

graph.addEgde(4, 5); | |

int source =0; | |

int destination=5; | |

graph.countPaths(source,destination); | |

} | |

} |

**Output**:

No of paths between source: 0 and destination: 5 are: 3