Shortest Path Algorithm Mock Test

Please wait while the activity loads.
If this activity does not load, try refreshing your browser. Also, this page requires javascript. Please visit using a browser with javascript enabled.

If loading fails, click here to try again

Question 1

Consider the following strategy to solve the single source shortest path problem with edge weights from source

s

.

1. Replace each edge with weight

w

w

edges of weight

1

connected by new intermediate nodes
2. Run BFS(s) on the modified graph to find the shortest path to each of the original vertices in the graph.

Which of the following statements is correct?

A	This strategy will not solve the problem correctly.
B	This strategy will only work if the graph is acyclic.
C	This strategy will solve the problem correctly and is as efficient as Dijkstra's algorithm.
D	This strategy will solve the problem correctly but is not as efficient as Dijkstra's algorithm.

Algorithm

Question 1 Explanation:

The strategy is sound, but the size of the graph will be proportional to the edge weights in the original graph, so the complexity will increase.

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

Click Here to Practice ALL Previous MOCK TEST FREE

Question 2

Consider the following strategy to convert an undirected graph with negative edge weights to one that does not have negative edge weights. Let the maximum magnitude negative edge weight in the graph be

-k

. Then, for each edge in the graph with weight

w

, update the weight to

w+k+1

. Consider the following claim:

To solve the shortest path problem in the original graph, we can run Dijkstra's algorithm on the modified graph and subtract the added weights to get the original distances.

Which of the following is NOT correct?

A	The claim is true for connected acyclic graphs.
B	The claim is true for all graphs.
C	The claim is not true in general for graphs with cycles.
D	The claim is not true in general.

Algorithm

Question 2 Explanation:

Adding a weight to each edge increases the weight of a path proportional to the number of edges, so "long" shortest paths (in terms no of edges) get penalized.
In a tree (connected acyclic graph), there is only one path between any pair of nodes, so the shortest path is invariant.

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

Click Here to Practice ALL Previous MOCK TEST FREE

Question 3

Suppose you have a directed acyclic graph with

n

vertices and

O(n)

edges, all having nonnegative weights. Running time (in form of

n

) of an efficient algorithm for finding the shortest path to each vertex from a single source is

A	$O(n)$
B	$O(n \log n)$
C	$O(n^2)$
D	$O(n^2 \log n)$

Algorithm

Question 3 Explanation:

The given conditions allow us to use either the DAG shortest paths algorithm or Dijkstra's. DAG shortest paths runs in

\Theta (V+E)=\Theta (n)

, and Dijkstra's runs in

O((V + E) \log V )

, or

O(V \log V + E)

if using a Fibonacci heap. In either case, Dijkstra's runs in

O(n \log n)

. DAG shortest paths is faster in this case
https://www.cs.bgu.ac.il/~ds182/wiki.files/14-shortest_paths.pdf

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

Click Here to Practice ALL Previous MOCK TEST FREE

Question 4

Which of the following Statemets is/are TRUE?

S1: Consider two positively weighted graphs

G = (V; E; w)

and

G_0 = (V; E; w_0)

with the same vertices

V

and edges

E

such that, for any edge

e

E

, we have

w_0(e) = w(e)^2

. For any two vertices

u, v

V

, any shortest path between

u

and

v

G_0

is also a shortest path in

G

.

S2: If the priority queue in Dijkstra's algorithm is implemented using a sorted linked list (where the list is kept sorted after each priority queue operation), then Dijkstra's algorithm would run in

O(ElgV +V lgV)

time.

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 4 Explanation:

S1 is FALSE
Assume we have two paths in

G

as (1)

path: u-x-v : 4

with

w(u,x)=2,w(x,v)=2

(2)path: u-v:3 with

w(u,v)=3

. The first one is shorter in

G_0

while the second one is shorter in

G

.

S2 is FLASE
The list can take

\Theta (V)

time to insert a node, and there are

(V)

nodes to insert, for a running time of

\Omega (V^2)

. In addition, the

\Theta (E)

calls to decrease-key can each take

\Theta (V)

time for a total running time of

\Theta ((V + E)V )

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

Click Here to Practice ALL Previous MOCK TEST FREE

Question 5

Which of the following Statemets is/are TRUE?

S1: Given a graph G = (V, E) with positive edge weights, the Bellman-Ford algorithm and Dijkstra's algorithm can produce different shortest-path trees despite always producing the same shortest-path weights.

S2: Dijkstra's algorithm may not terminate if the graph contains negative-weight

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 5 Explanation:

S1 is TRUE
Both algorithms are guaranteed to produce the same shortestpath weight, but if there are multiple shortest paths, Dijkstra's will choose the shortest path according to the greedy strategy, and Bellman-Ford will choose the shortest path depending on the order of relaxations, and the two shortest path trees may be different.

S2 is FLASE
It always terminates after |E| relaxations and |V|+|E| priority queue operations, but may produce incorrect results.

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

Click Here to Practice ALL Previous MOCK TEST FREE