{"id":"713b616d-87a4-4812-b324-63938bfb8ed1","name":"Print All Paths","description":"<p>1. You are given a graph, a source vertex and a destination vertex. 2. You are required to find and print all paths between source and destination. Print them in lexicographical order. E.g. Check the following paths 012546 01256 032546 03256 The lexicographically smaller path is printed first.</p>","inputFormat":"Input has been managed for you","outputFormat":"Check sample output","constraints":"None","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\n\nusing namespace std;\n class Edge {\n public:\n int src;\n int nbr;\n int wt;\n\n Edge(int src, int nbr, int wt){\n this->src = src;\n this->nbr = nbr;\n this->wt = wt;\n }\n };\n \n \n int main(){\n int vtces;\n cin>>vtces;\n vector<Edge>graph[vtces];\n\n int edges;\n cin>>edges;\n for(int i = 0; i < edges; i++){\n int v1 ;\n int v2 ;\n int wt ;\n cin>>v1>>v2>>wt;\n graph[v1].push_back( Edge(v1, v2, wt));\n graph[v2].push_back( Edge(v2, v1, wt));\n }\n\n int src;\n cin>>src;\n int dest;\n cin>>dest;\n // write your code here\n \n }"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n static class Edge {\r\n int src;\r\n int nbr;\r\n int wt;\r\n\r\n Edge(int src, int nbr, int wt) {\r\n this.src = src;\r\n this.nbr = nbr;\r\n this.wt = wt;\r\n }\r\n }\r\n\r\n public static void main(String[] args) throws Exception {\r\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\r\n\r\n int vtces = Integer.parseInt(br.readLine());\r\n ArrayList<Edge>[] graph = new ArrayList[vtces];\r\n for (int i = 0; i < vtces; i++) {\r\n graph[i] = new ArrayList<>();\r\n }\r\n\r\n int edges = Integer.parseInt(br.readLine());\r\n for (int i = 0; i < edges; i++) {\r\n String[] parts = br.readLine().split(\" \");\r\n int v1 = Integer.parseInt(parts[0]);\r\n int v2 = Integer.parseInt(parts[1]);\r\n int wt = Integer.parseInt(parts[2]);\r\n graph[v1].add(new Edge(v1, v2, wt));\r\n graph[v2].add(new Edge(v2, v1, wt));\r\n }\r\n\r\n int src = Integer.parseInt(br.readLine());\r\n int dest = Integer.parseInt(br.readLine());\r\n\r\n // write all your codes here\r\n }\r\n\r\n\r\n}"},"python":{"code":"class Edge:\n def __init__(self, src, nbr, wt):\n self.src = src\n self.nbr = nbr\n self.wt = wt\n\n\ndef main():\n vtces = int(input())\n edges = int(input())\n graph = {}\n for i in range(vtces):\n graph[i] = []\n\n for i in range(edges):\n values = input().split(\" \")\n v1 = int(values[0])\n v2 = int(values[1])\n wt = int(values[2])\n e1 = Edge(v1, v2, wt)\n e2 = Edge(v2, v1, wt)\n graph[e1.src].append(e1)\n graph[e2.src].append(e2)\n\n src = int(input())\n dest = int(input())\n\n # write your code here\n\n\nif __name__ == \"__main__\":\n main()"}},"points":10,"difficulty":"easy","sampleInput":"7\r\n8\r\n0 1 10\r\n1 2 10\r\n2 3 10\r\n0 3 10\r\n3 4 10\r\n4 5 10\r\n5 6 10\r\n4 6 10\r\n0\r\n6","sampleOutput":"0123456\r\n012346\r\n03456\r\n0346","questionVideo":"https://www.youtube.com/embed/DrQ-eTN2v3A?start=0&end=85","hints":[],"associated":[{"id":"beab4942-e2c7-422c-a266-f737365b26e9","name":"What is the space complexity of \"Print All Paths\" approach?","slug":"what-is-the-space-complexity-of-print-all-paths-approach","type":4},{"id":"e362a728-1ee1-45bd-8f0c-d1eb326b9d00","name":"What is the time complexity of \"Print All Paths\" approach?","slug":"what-is-the-time-complexity-of-print-all-paths-approach","type":4},{"id":"e5cb6ff4-8155-43c1-a670-51070b87258a","name":"What will be the base case for \"Print All Paths\" question?","slug":"what-will-be-the-base-case-for-print-all-paths-question","type":4}],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"02ab8fe3-cddd-43ad-b241-b8b1a2fcd52e","name":"Graphs For Beginners","slug":"graphs-for-beginners","type":0},{"id":"c6187ede-6167-470c-af41-9a7bf6b8ad1c","name":"Print All Paths","slug":"print-all-paths","type":1}],"next":{"id":"4cc53964-8fd2-4935-b56c-65f4cac3ee0a","name":"Print All Path","type":3,"slug":"print-all-path"},"prev":{"id":"88f3e4e7-65b2-40e4-9c64-f6242756faf3","name":"Has Path.","type":3,"slug":"has-path"}}}

Print All Paths

<p>1. You are given a graph, a source vertex and a destination vertex. 2. You are required to find and print all paths between source and destination. Print them in lexicographical order. E.g. Check the following paths 012546 01256 032546 03256 The lexicographically smaller path is printed first.</p>

{"id":"713b616d-87a4-4812-b324-63938bfb8ed1","name":"Print All Paths","description":"<p>1. You are given a graph, a source vertex and a destination vertex. 2. You are required to find and print all paths between source and destination. Print them in lexicographical order. E.g. Check the following paths 012546 01256 032546 03256 The lexicographically smaller path is printed first.</p>","inputFormat":"Input has been managed for you","outputFormat":"Check sample output","constraints":"None","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\n\nusing namespace std;\n class Edge {\n public:\n int src;\n int nbr;\n int wt;\n\n Edge(int src, int nbr, int wt){\n this->src = src;\n this->nbr = nbr;\n this->wt = wt;\n }\n };\n \n \n int main(){\n int vtces;\n cin>>vtces;\n vector<Edge>graph[vtces];\n\n int edges;\n cin>>edges;\n for(int i = 0; i < edges; i++){\n int v1 ;\n int v2 ;\n int wt ;\n cin>>v1>>v2>>wt;\n graph[v1].push_back( Edge(v1, v2, wt));\n graph[v2].push_back( Edge(v2, v1, wt));\n }\n\n int src;\n cin>>src;\n int dest;\n cin>>dest;\n // write your code here\n \n }"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n static class Edge {\r\n int src;\r\n int nbr;\r\n int wt;\r\n\r\n Edge(int src, int nbr, int wt) {\r\n this.src = src;\r\n this.nbr = nbr;\r\n this.wt = wt;\r\n }\r\n }\r\n\r\n public static void main(String[] args) throws Exception {\r\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\r\n\r\n int vtces = Integer.parseInt(br.readLine());\r\n ArrayList<Edge>[] graph = new ArrayList[vtces];\r\n for (int i = 0; i < vtces; i++) {\r\n graph[i] = new ArrayList<>();\r\n }\r\n\r\n int edges = Integer.parseInt(br.readLine());\r\n for (int i = 0; i < edges; i++) {\r\n String[] parts = br.readLine().split(\" \");\r\n int v1 = Integer.parseInt(parts[0]);\r\n int v2 = Integer.parseInt(parts[1]);\r\n int wt = Integer.parseInt(parts[2]);\r\n graph[v1].add(new Edge(v1, v2, wt));\r\n graph[v2].add(new Edge(v2, v1, wt));\r\n }\r\n\r\n int src = Integer.parseInt(br.readLine());\r\n int dest = Integer.parseInt(br.readLine());\r\n\r\n // write all your codes here\r\n }\r\n\r\n\r\n}"},"python":{"code":"class Edge:\n def __init__(self, src, nbr, wt):\n self.src = src\n self.nbr = nbr\n self.wt = wt\n\n\ndef main():\n vtces = int(input())\n edges = int(input())\n graph = {}\n for i in range(vtces):\n graph[i] = []\n\n for i in range(edges):\n values = input().split(\" \")\n v1 = int(values[0])\n v2 = int(values[1])\n wt = int(values[2])\n e1 = Edge(v1, v2, wt)\n e2 = Edge(v2, v1, wt)\n graph[e1.src].append(e1)\n graph[e2.src].append(e2)\n\n src = int(input())\n dest = int(input())\n\n # write your code here\n\n\nif __name__ == \"__main__\":\n main()"}},"points":10,"difficulty":"easy","sampleInput":"7\r\n8\r\n0 1 10\r\n1 2 10\r\n2 3 10\r\n0 3 10\r\n3 4 10\r\n4 5 10\r\n5 6 10\r\n4 6 10\r\n0\r\n6","sampleOutput":"0123456\r\n012346\r\n03456\r\n0346","questionVideo":"https://www.youtube.com/embed/DrQ-eTN2v3A?start=0&end=85","hints":[],"associated":[{"id":"beab4942-e2c7-422c-a266-f737365b26e9","name":"What is the space complexity of \"Print All Paths\" approach?","slug":"what-is-the-space-complexity-of-print-all-paths-approach","type":4},{"id":"e362a728-1ee1-45bd-8f0c-d1eb326b9d00","name":"What is the time complexity of \"Print All Paths\" approach?","slug":"what-is-the-time-complexity-of-print-all-paths-approach","type":4},{"id":"e5cb6ff4-8155-43c1-a670-51070b87258a","name":"What will be the base case for \"Print All Paths\" question?","slug":"what-will-be-the-base-case-for-print-all-paths-question","type":4}],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"02ab8fe3-cddd-43ad-b241-b8b1a2fcd52e","name":"Graphs For Beginners","slug":"graphs-for-beginners","type":0},{"id":"c6187ede-6167-470c-af41-9a7bf6b8ad1c","name":"Print All Paths","slug":"print-all-paths","type":1}],"next":{"id":"4cc53964-8fd2-4935-b56c-65f4cac3ee0a","name":"Print All Path","type":3,"slug":"print-all-path"},"prev":{"id":"88f3e4e7-65b2-40e4-9c64-f6242756faf3","name":"Has Path.","type":3,"slug":"has-path"}}}
plane

Editor

Loading...

Print All Paths

easy

1. You are given a graph, a source vertex and a destination vertex. 2. You are required to find and print all paths between source and destination. Print them in lexicographical order. E.g. Check the following paths 012546 01256 032546 03256 The lexicographically smaller path is printed first.

Constraints

None

Format

Input

Input has been managed for you

Output

Check sample output

Example

Sample Input

7 8 0 1 10 1 2 10 2 3 10 0 3 10 3 4 10 4 5 10 5 6 10 4 6 10 0 6

Sample Output

0123456 012346 03456 0346

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode