> 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;
    }
}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://mayanktyagi3111.gitbook.io/interview-prep/graphs-bfs-and-dfs/all-paths-from-source-lead-to-destination.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.