This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Shortest Paths”.
1. Which is the correct technique for finding a maximum matching in a graph?
a) BFS traversal
b) DFS traversal
c) Shortest path traversal
d) Heap order traversal
View Answer
Explanation: The correct technique for finding a maximum matching in a bipartite graph is by using a Breadth First Search(BFS).
2. What is the running time of an unweighted shortest path algorithm whose augmenting path is the path with the least number of edges?
a) O(|E||V|)
b) O(|E|)
c) O(|E| log |V|)
d) O(|E|2|V|)
View Answer
Explanation: Each augmenting step takes O(|E|) using an unweighted shortest path algorithm yielding a O(|E|2|V|) bound on the running time.
3. Floyd Warshall Algorithm can be used for finding _____________
a) Transitive closure
b) Minimum spanning tree
c) Topological sort
d) Single source shortest path
View Answer
Explanation: One of the ways to compute the transitive closure of a graph in Theta(N3) time is to assign a weight of 1 to each edge of E and then run the Floyd Warshall Algorithm.
4. Bellmann ford algorithm provides solution for ____________ problems.
a) Network flow
b) Single source shortest path
c) All pair shortest path
d) Sorting
View Answer
Explanation: Bellmann ford algorithm is used for finding solutions for single source shortest path problems. If the graph has no negative cycles that are reachable from the source then the algorithm produces the shortest paths and their weights.
5. What is the pseudo code to compute the shortest path in Dijkstra’s algorithm?
a)
if(T[w].Known) if(T[v].Dist + C(v,w) < T[w].Dist) { Increase (T[w].Dist to T[v].Dist +C(v,w)); T[w].path=v; }
b)
if(!T[w].Known) if(T[v].Dist + C(v,w) > T[w].Dist) { Decrease(T[w].Dist to T[v].Dist +C(v,w); T[w].path=v; }
c)
if(!T[w].Known) if(T[v].Dist + C(v,w) < T[w].Dist) { Decrease(T[w].Dist to T[v].Dist +C(v,w)); T[w].path=v; }
d)
if(T[w].Known) if(T[v].Dist + C(v,w) < T[w].Dist) { Increase(T[w].Dist to T[v].Dist); T[w].path=v; }
Explanation: If the known value of the adjacent vertex(w) is not set then check whether the sum of distance from source vertex(v) and cost to travel from source to adjacent vertex is less than the existing distance of the adjacent node. If so, perform decrease key operation.
6. Dijkstra’s Algorithm is used to solve _____________ problems.
a) Single source shortest path
b) All pair shortest path
c) Sorting
d) Network flow
View Answer
Explanation: Dijkstra’s Algorithm is used for solving single source shortest path problems. In this algorithm, a single node is fixed as a source node and shortest paths from this node to all other nodes in graph is found.
7. What approach is being followed in Floyd Warshall Algorithm?
a) Linear Programming
b) Backtracking
c) Greedy technique
d) Dynamic Programming
View Answer
Explanation: Floyd Warshall Algorithm follows dynamic programming approach because the all pair shortest paths are computed in bottom up manner.
8. Which of the following is not an application of Breadth First Search?
a) Path Finding
b) Finding bipartiteness of a graph
c) GPS navigation system
d) Finding shortest path between two nodes
View Answer
Explanation: Breadth First Search can be applied to Bipartite a graph, to find the shortest path between two nodes, in GPS Navigation. In Path finding, Depth First Search is used.
9. Chan’s algorithm is used for computing _________
a) Shortest path between two points
b) Area of a polygon
c) Convex hull
d) Closest distance between two points
View Answer
Explanation: Chan’s algorithm is an output-sensitive algorithm used to compute the convex hull set of n points in a 2D or 3D space. Closest pair algorithm is used to compute the closest distance between two points.
More MCQs on Shortest Paths:
Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.
To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.
