# Shortest Paths Multiple Choice Questions (MCQ)

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

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|)

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

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

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

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

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
d) Finding shortest path between two nodes

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

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.

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]