Question:
An undirected weighted graph $ G $ is shown (not included here, but described in text). Find the set of all positive integer values of $ x $ such that if we use Dijkstra’s algorithm, there will be a unique shortest path from vertex $ a $ to vertex $ j $ that contains the edge $ (b, e) $.
Options:
(a) ${x \mid x \in \mathbb{Z}, 0 < x < 8}$
(b) ${x \mid x \in \mathbb{Z}, 0 < x < 7}$
(c) ${x \mid x \in \mathbb{Z}, 0 < x < 6}$
(d) ${x \mid x \in \mathbb{Z}, 0 < x < 9}$
Solution:
If edge $ (b, e) $ is not considered, the shortest path is $ 2+4+3+1+2+1 = 13 $. For the path through $ (b, e) $ to be the unique shortest path:
$$
2 + x + 1 + 2 + 1 = x + 6 < 13 \implies x < 7
$$
Answer: (b) ${x \mid x \in \mathbb{Z}, 0 < x < 7}$
2. Shortest Path Algorithms and Negative Weights
Question:
An undirected graph $ G $ is shown (weights include negative values). Suppose we are trying to perform an algorithm to find the shortest path from vertex $ v_0 $ to $ v_4 $. Which of the following statements is (are) correct?
(a) Dijkstra’s algorithm can be used to find the shortest path from $ v_0 $ to $ v_4 $.
(b) Bellman-Ford algorithm can be used to find the shortest path from $ v_0 $ to $ v_4 $ because there are negative weighted edges.
(c) The weight of the shortest path from $ v_0 $ to $ v_4 $ is 1.
(d) Bellman-Ford algorithm cannot be used to find the shortest path from $ v_0 $ to $ v_4 $ because there is a negative cycle in the given graph.
Solution:
There is a negative cycle: $ v_0 \rightarrow v_1 \rightarrow v_2 \rightarrow v_7 \rightarrow v_0 $.
Correct: (d) Bellman-Ford algorithm cannot be used to find the shortest path from $ v_0 $ to $ v_4 $ because there is a negative cycle in the given graph.
3. Incorrect Statements about Graphs
Question:
Which of the following statements is (are) INCORRECT?
(a) In an undirected graph $ G $, if all edges have different positive weights, then the minimum cost spanning tree of graph $ G $ is unique.
(b) If there is a cycle of weight 0 in a directed graph $ G $, then we cannot find the shortest path using Bellman-Ford algorithm.
(c) Suppose an acyclic undirected graph $ G $ with $ n $ vertices has $ n-1 $ edges. Then the graph is connected.
(d) In a graph $ G $, every edge with the minimum weight will be in the minimum cost spanning tree.
Solution:
(a): Correct (unique if all weights are distinct).
(b): Incorrect (Bellman-Ford can be used unless there is a negative cycle).
(c): Correct (acyclic with $ n-1 $ edges is a tree and connected).
(d): Incorrect (not every minimum weight edge is in the MST; counterexample shown).
Answer: (b), (d)
4. Cheapest Flight Route
Question:
A company has branches in each of six cities $ C_0, C_1, ···, C_5 $. The fare (in thousands of rupees) for a direct flight from $ C_i $ to $ C_j $ is given by a matrix (not shown here). An employee wants to travel from $ C_2 $ to $ C_5 $. If he travels by the cheapest route possible, what is the total fare he paid for the flight journey?
Solution:
Using Dijkstra’s algorithm, the minimum fare from $ C_2 $ to $ C_5 $ is 15 (thousand rupees).
Answer: 15 (i.e., ₹15,000)
5. Inspection Route with Minimum Fare
Question:
If an inspection team member wanted to inspect all the branches of the company starting from $ C_2 $ and ending at $ C_5 $, visiting each branch exactly once, then which of the following routes should he choose in order to pay minimum fare for flight journey?
(a) $ C_2 \rightarrow C_3 \rightarrow C_1 \rightarrow C_0 \rightarrow C_4 \rightarrow C_5 $
(b) $ C_2 \rightarrow C_1 \rightarrow C_3 \rightarrow C_4 \rightarrow C_0 \rightarrow C_5 $
(c) $ C_2 \rightarrow C_3 \rightarrow C_1 \rightarrow C_4 \rightarrow C_0 \rightarrow C_5 $
(d) Such a route is not possible.
Solution:
No such route is possible (as per the solution, some connections are missing).
Answer: (d) Such a route is not possible.
6. Minimum Spanning Tree (MST) Cost
Question:
Seven computers ${C_0, C_2, \ldots, C_6}$ are linked by a network, and each link has a maintenance cost (shown in graph). The goal is to pick a subset of links such that the total maintenance cost is minimum and the computers remain connected. What is the total maintenance cost (in hundreds of rupees) of the optimum subset of links?
Solution:
Using Prim’s or Kruskal’s algorithm, the minimum cost is $1+2+1+2+4+5 = 15$ (hundred rupees).
Answer: 15
7. Number of Different MSTs
Question:
Find the number of different ways of choosing an optimum subset of links for the given graph.
Solution:
There are 4 different ways to choose the MST (as per the solution, two with red/blue links and two with green/dark blue links).
Answer: 4
8. Prim’s Algorithm Order
Question:
Consider a weighted graph $ G $ with 7 vertices ${A, B, C, D, E, F, G}$, represented by the following adjacency matrix (not shown here). Suppose we perform Prim’s algorithm on the graph $ G $ starting from vertex $ A $ to find an MCST. Then the order in which the vertices are added is:
(a) $ A, C, F, G, B, D, E $
(b) $ A, B, D, E, G, C, F $
(c) $ A, B, G, C, F, D, E $
(d) $ A, C, F, G, E, D, B $
Solution:
The correct order is $ A, B, G, C, F, D, E $.
Answer: (c)
9. Kruskal’s Algorithm and Excluded Edges
Question:
Suppose we perform Kruskal’s algorithm on the graph $ G $ starting from vertex $ C $ to find an MCST. Which of the following edges are not added to the minimum cost spanning tree?
(a) $ (A, E) $
(b) $ (B, D) $
(c) $ (G, F) $
(d) $ (A, G) $
Solution:
Edges $ (G, F) $ and $ (A, E) $ are not added to the MST (they would form cycles).
Answer: (a), (c)
