> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/graphs-bfs-and-dfs/all-paths-from-source-lead-to-destination.md).

# All Paths from Source Lead to Destination

Given the `edges` of a directed graph, and two nodes `source` and `destination` of this graph, determine whether or not all paths starting from `source` eventually end at `destination`, that is:

* At least one path exists from the `source` node to the `destination` node
* If a path exists from the `source` node to a node with no outgoing edges, then that node is equal to `destination`.
* The number of possible paths from `source` to `destination` is a finite number.

Return `true` if and only if all roads from `source` lead to `destination`.

**Example 1:**

![](https://miro.medium.com/max/420/0*r77DDXxperMy1J59.png)

```
Input: n = 3, edges = [[0,1],[0,2]], source = 0, destination = 2
Output: false
Explanation: It is possible to reach and get stuck on both node 1 and node 2.
```

**Example 2:**

![](https://miro.medium.com/max/420/0*SzITWx1jWve9dyNH.png)

```
Input: n = 4, edges = [[0,1],[0,3],[1,2],[2,1]], source = 0, destination = 3
Output: false
Explanation: We have two possibilities: to end at node 3, or to loop over node 1 and node 2 indefinitely.
```

**Example 3:**

![](https://miro.medium.com/max/410/0*6Ohc1ZujuilV5DnR.png)

```
Input: n = 4, edges = [[0,1],[0,2],[1,3],[2,3]], source = 0, destination = 3
Output: true
```

**Example 4:**

![](https://miro.medium.com/max/410/0*UaGShUzZNCiShLfB.png)

```
Input: n = 3, edges = [[0,1],[1,1],[1,2]], source = 0, destination = 2
Output: false
Explanation: All paths from the source node end at the destination node, but there are an infinite number of paths, such as 0-1-2, 0-1-1-2, 0-1-1-1-2, 0-1-1-1-1-2, and so on.
```

**Example 5:**

![](https://miro.medium.com/max/270/0*wvLwyxz_A96QY-N6.png)

```
Input: n = 2, edges = [[0,1],[1,1]], source = 0, destination = 1
Output: false
Explanation: There is infinite self-loop at destination node.
```

**Note:**

1. The given graph may have self-loops and parallel edges.
2. The number of nodes `n` in the graph is between `1` and `10000`
3. The number of edges in the graph is between `0` and `10000`
4. `0 <= edges.length <= 10000`
5. `edges[i].length == 2`
6. `0 <= source <= n - 1`
7. `0 <= destination <= n - 1`

```java
public class PathsFromSourceToDest {
    public boolean leadsToDestination(int n, int[][] edges, int source, int destination) {
        // Creating graph
        List<Integer>[] graph = new ArrayList[n];
        for (int i = 0; i < n; i++)
            graph[i] = new ArrayList<>();
        for (int[] edge : edges)
            graph[edge[0]].add(edge[1]);
        // BFS
        boolean[] visited = new boolean[n];
        Queue<Integer> q = new LinkedList<>();
        q.add(source);
        while (!q.isEmpty()) {
            int node = q.poll();
            if (node == destination) {
                // The destination node should not have any outgoing edges
                // to be considered valid
                if (graph[node].size() != 0)
                    return false;
            }
            visited[node] = true;
            // If the current node is dead end, but not destination
            // Then asnwer is false. because we need All want to check whether all the paths
            // from source lead to ONLY destination
            if (graph[node].size() == 0)
                return false;

            for (int neighbor : graph[node]) {
                // Make sure that no cycles are forming,
                // because that will return in infinite paths
                if (!visited[neighbor])
                    q.add(next);
                else
                    return false;
            }
        }
        return true;
    }
}
```