Shortest Path Algorithm Mock Test – 1

Question 1
Given a weighted directed graph G = (V, E, w) and a shortest path p from s to t,

Consider the following statements

S1: if we doubled the weight of every edge to produce G'= (V, E, w'), then p is also a shortest path in G'.

S2 : if we increase the weight of every edge by constant c to produce G'= (V, E, w'), then p is also a shortest path in G'.
A
S1 is True and S2 is False
B
S1 is False and S2 is True
C
S1 and S2 are False
D
S1 and S2 are True
   Algorithm
Question 1 Explanation: 
S1 is True.
Multiplying edge weights by any positive constant factor preserves their relative order, as well as the relative order of any linear combination of the weights. All path weights are linear combinations of edge weights, so the relative order of path weights is preserved. This means that a shortest path in G will still be a shortest path in G'.

The shortest path remains same. It is like if we change unit of distance from meter to kilometer, the shortest paths don't change.
S2 is false.
consider the following counter-example.
Let a graph contain only the following 2 paths-: S-W-T and S-A-B-T.
Let the weights of the edges be -:
S-W:2
W-T:2
S-A:1
A-B:1
B-T:1

Now the shortest path between S-T is S-A-B-T. Now add a weight of 5 (c=5) to all edges, and convince yourself the new shortest path will be S-W-T.

Click to Join Our Telegram Group for Latest Update of MOCK TEST

Click Here to Practice ALL Previous MOCK TEST FREE
Question 2
An airline charges a fixed price for each direct flight. For each sequence of hopping flights, the ticket price is the sum of the fares of the individual sectors.

TripGuru has precalculated the cheapest routes between all pairs of cities so that it can offer an optimum choice instantly to customers visiting its website.

Overnight, the government has added a 13% luxury service surcharge to the cost of each. Which of the following describes the impact of this surcharge on TripGuru's computation?
A
There is no impact. Cheapest routes between all pairs of cities remains unchanged.
B
The surcharge favours hopping flights with fewer sectors. TripGuru should recompute any cheapest route where there is a shorter route in terms of number of flights.
C
The surcharge favours hopping flights with more sectors. TripGuru should recompute any cheapest route where there is a longer route in terms of number of flights.
D
The impact is unpredictable. TripGuru should recompute all cheapest routes.
   Algorithm
Question 2 Explanation: 
Second way of asking the question on shortest path when we multiply constant with all edge's weight.
Multiplying edge weights by any positive constant factor preserves their relative order, as well as the relative order of any linear combination of the weights. All path weights are linear combinations of edge weights, so the relative order of path weights is preserved. This means that a shortest path in G will still be a shortest path in G'.

The shortest path remains same. It is like if we change unit of distance from meter to kilometer, the shortest paths don't change.

Click to Join Our Telegram Group for Latest Update of MOCK TEST

Click Here to Practice ALL Previous MOCK TEST FREE
Source : NPTEL Course Assignment
Question 3
An airline charges a fixed price for each direct flight. For each sequence of hopping flights, the ticket price is the sum of the fares of the individual sectors.

TripGuru has precalculated the cheapest routes between all pairs of cities on this airline's route network so that it can offer an optimum choice instantly to customers visiting its website.

The airline has decided to become a full-service carrier and has included a meal on each sector. To account for this, the airline has added a flat "convenience fee" of Rs 300 on each sector.

Which of the following describes the impact of this surcharge on TripGuru's computation?
A
There is no impact. Cheapest routes between all pairs of cities remains unchanged.
B
The surcharge favours hopping flights with fewer sectors. TripGuru should recompute any cheapest route where there is a shorter route in terms of number of flights.
C
The surcharge favours hopping flights with more sectors. TripGuru should recompute any cheapest route where there is a longer route in terms of number of flights.
D
The impact is unpredictable. TripGuru should recompute all cheapest routes.
   Algorithm
Question 3 Explanation: 
The cost per edge increases, so the price for a path with n hops increases by 300n. This means that a shorter path incurs a smaller penalty, so a longer "shortest" path in the original graph may be superseded by a shorter one after adding the penalty on each edge.

Accepted Answers:
The surcharge favours hopping flights with fewer sectors. TripGuru should recompute any cheapest route where there is a shorter route in terms of number of flights.

Click to Join Our Telegram Group for Latest Update of MOCK TEST

Click Here to Practice ALL Previous MOCK TEST FREE
Source : NPTEL Course Assignment
Question 4
Consider a graph G. Let T be a BFS tree with root r. Let d(u,v) denote the length of the shortest path between the nodes u and v. If v is visited before u in the breadth first search traversal, which of the following statements is true ?
A
d(r,v) > d(r,u)
B
d(r,v) = d(r,u)
C
d(r,v) < d(r,u)
D
insufficient information to comment on d(r,v) and d(r,u)
   Algorithm
Question 4 Explanation: 
u being traversed after v does not tell us if they are on the same level or not. The correct relation would be d(r,v) <= d(r,u)

Click to Join Our Telegram Group for Latest Update of MOCK TEST

Click Here to Practice ALL Previous MOCK TEST FREE
Question 5
Let G = (V, E) be a simple undirected graph, and s be a particular vertex in it called the source. For x \in V, let d(x) denote the shortest distance in G from s to x. A breadth first search (BFS) is performed starting at s. Let T be the resultant BFS tree. If (u,v) is an edge of G that is not in T, then which one of the following CANNOT be the value of d(u)-d(v)?
A
-1
B
0
C
1
D
2
   Algorithm
Question 6
Let T be a tree constructed by Dijkstra's algorithm in the process of solving the single source shortest-paths problem for a weighted connected graph G.

Consider the following statements

S1: T is a spanning tree of G.
S2: T is a minimum spanning tree of G.
A
S1 is True and S2 is False
B
S1 is False and S2 is True
C
S1 and S2 are False
D
S1 and S2 are True
   Algorithm
Question 6 Explanation: 
Consider the following example to understand the concept

Vertices: {P,Q,R}
Edges: (undirected) {P,Q,4} {P,R,3} {Q,R,2}
So basically it's a triangle with the given weights. Starting from P, Dijkstra's algorithm will give you (P,Q) and (P,R) but the minimum spanning Tree will give you (P,R) and (Q,R).
Hence, S1 is true but S2 is false.

Click to Join Our Telegram Group for Latest Update of MOCK TEST

Click Here to Practice ALL Previous MOCK TEST FREE
Question 7
Given a weighted graph G where weights of all edges are unique (no two edge have same weights),

Consider the following statements

S1 : There is always a unique shortest path from a source to destination in such a graph.
S2: There is always a unique MST of graph G.
A
S1 is True and S2 is False
B
S1 is False and S2 is True
C
S1 and S2 are False
D
S1 and S2 are True
   Algorithm
Question 7 Explanation: 
Consider the following example to understand the concept

Vertices: {P,Q,R}
Edges: (undirected) {P,Q,1} {P,R,3} {Q,R,2}


Click to Join Our Telegram Group for Latest Update of MOCK TEST

Click Here to Practice ALL Previous MOCK TEST FREE
Question 8
Consider the following statements

S1 : A graph can have more than one shorstest path between two vertices
S2 : A graph, where all edges weitght are distinct can have more than one shorstest path between two vertices.
A
S1 is True and S2 is False
B
S1 is False and S2 is True
C
S1 and S2 are False
D
S1 and S2 are True
   Algorithm
Question 8 Explanation: 
Consider the following example to understand the concept

Vertices: {P,Q,R}
Edges: (undirected) {P,Q,1} {P,R,3} {Q,R,2}


Click to Join Our Telegram Group for Latest Update of MOCK TEST

Click Here to Practice ALL Previous MOCK TEST FREE
Question 9
If all edges have the same weight in an undirected graph, which algorithm will find the shortest path between two nodes more efficiently?
A
Dijkstra
B
Bellman-Ford
C
Depth-First Search
D
Breadth-First Search
   Algorithm
Question 9 Explanation: 
Breadth-First Search has time complexity O(|V| + |E|).

Click to Join Our Telegram Group for Latest Update of MOCK TEST

Click Here to Practice ALL Previous MOCK TEST FREE
Question 10
To implement Dijkstra?s shortest path algorithm on unweighted graphs so that it runs in linear time, the data structure to be used is:
A
Stack
B
Queue
C
Heap
D
Binary Tree
   Algorithm
Question 10 Explanation: 
If we use Queue (FIFO) instead of Priority Queue (Min Heap), we get the shortest path in linear time O(|V| + |E|).

Click to Join Our Telegram Group for Latest Update of MOCK TEST

Click Here to Practice ALL Previous MOCK TEST FREE
There are 10 questions to complete.

Leave a Comment