Question:
Let G be a directed graph whose vertex set is the set of numbers from 1 to 100. There is an edge from a vertex i to j if and only if either j = i + 1 or j = 3i. The minimum number of edges in a path in G from vertex 1 to vertex 100 is:
Let G be a directed graph whose vertex set is the set of numbers from 1 to 100. There is an edge from a vertex i to j if and only if either j = i + 1 or j = 3i. The minimum number of edges in a path in G from vertex 1 to vertex 100 is:
Show Hint
When solving shortest path problems: Use BFS or Dijkstra’s algorithm for directed graphs and Understand the edge conditions carefully.
Updated On: Dec 29, 2024
- 4
- 7
- 23
- 99
Hide Solution
Verified By Collegedunia
The Correct Option is B
Solution and Explanation
The problem can be solved using Breadth-First Search (BFS) to determine the shortest path. The total number of edges is: 4 + 3 = 7.
Was this answer helpful?
0
0
Top Questions on Algorithm
- Consider the following algorithm:
What will be the output (O/P) of this algorithm? - Consider the following graph with heuristic values: Which of the following represents the correct order of node expansion using the A* search algorithm?
- Which of the following data structures supports binary search in \( O(\log n) \) time complexity?
- When does the worst case of binary search occur?
- Suppose that insertion sort is applied to the array \([1,2,3,5,7,9,11,x,15,13]\) and it takes exactly 2 swaps to sort the array. Select all possible values of \( x \).
View More Questions
Questions Asked in CUET PG exam
- What is the antonym of eradicate?
- CUET (PG) - 2025
- Antonyms
- Who was the first Secretary-General of the UN?
- CUET (PG) - 2025
- United Nations and its Organizations
- What is the correct verb form: He, as well as his friends, ?
- Which preposition is correct: Chanakya lived ?
- CUET (PG) - 2025
- Prepositions
- Identify the possessive noun: My office car is parked elsewhere.
View More Questions