All Paths From Source Lead To Destination Problem Statement

In a directed graph with 'N' nodes numbered from 0 to N-1, determine whether every possible path starting from a given source node (SRC) eventually leads to a specified destination node (DEST). You are provided with a list of edges representing the connections between nodes, along with the node SRC and DEST.

Conditions:

  • There must be at least one path from SRC to DEST.
  • If there's a path from SRC to any node with no outgoing edges, that node should be DEST.
  • The number of paths from SRC to DEST should be finite.

Return True if all paths starting at SRC end at DEST, otherwise return False.

Example:

Input:
 N = 4, EDGES = [[0, 1], [0, 3], [1, 2], [3, 2]], SRC = 0, DEST = 2
Output:
True
Explanation:

All paths originating from node 0 lead to node 2 (DEST) as follows: 0->1->2 and 0->3->2. Since both paths eventually end at the destination node 2, the result is True.

Constraints:

  • 1 <= T <= 50
  • 2 <= N <= 104
  • 0 <= M <= 104
  • 0 <= SRC < N
  • 0 <= DEST < N
  • SRC ≠ DEST
  • 0 <= EDGES[i][j] < N

Input:

 The first line contains the integer 'T', the number of test cases. For each test case: the first line has four space-separated integers: 'N', 'M', 'SRC', 'DEST'. Following are 'M' lines, each with two integers representing a directed edge. 

Output:

 Print 'True' for each test case if every path from SRC leads to DEST, else print 'False'. Each test case result should be on a new line. 

Note:

 No need to print anything. Your task is to implement the function that determines the result. 
AnswerBot
4mo

Determine if all paths from a source node lead to a destination node in a directed graph.

  • Check if there is at least one path from source to destination.

  • If a node has no outgoing edges, it should be th...read more

Help your peers!
Select
Add answer anonymously...

American Express Software Developer interview questions & answers

A Software Developer was asked 7mo agoQ. Write a program to print prime numbers from 1 to n.
A Software Developer was asked 9mo agoQ. Write a function to determine if an array of numbers are prime using streams.
A Software Developer was asked 11mo agoQ. How have you leveraged Spring Java in your projects?

Popular interview questions of Software Developer

A Software Developer was asked 7mo agoQ1. Write a program to print prime numbers from 1 to n.
A Software Developer was asked 9mo agoQ2. Write a function to determine if an array of numbers are prime using streams.
A Software Developer was asked Q3. How do you implement security in microservices?
American Express Software Developer Interview Questions
Stay ahead in your career. Get AmbitionBox app
play-icon
play-icon
qr-code
Trusted by over 1.5 Crore job seekers to find their right fit company
80 L+

Reviews

10L+

Interviews

4 Cr+

Salaries

1.5 Cr+

Users

Contribute to help millions

Made with ❤️ in India. Trademarks belong to their respective owners. All rights reserved © 2025 Info Edge (India) Ltd.

Follow Us
  • Youtube
  • Instagram
  • LinkedIn
  • Facebook
  • Twitter
Profile Image
Hello, Guest
AmbitionBox Employee Choice Awards 2025
Winners announced!
awards-icon
Contribute to help millions!
Write a review
Write a review
Share interview
Share interview
Contribute salary
Contribute salary
Add office photos
Add office photos
Add office benefits
Add office benefits