Question 1

In the given graph, if we try to find the shortest path from node P to all other nodes using Figure from the original question paper **Dijkstra’s algorithm**, which node is the\ node to be included in the visited set? Consider that P is the **1st** visited node. Figure from the original question paper Consider the following algorithm to solve the **single source shortest path** problem for a graph (directed or undirected) with positive integer edge weights and a source vertex s.Replace each edge (u,v) of weight w in the graph with a path of length w consisting of unit-weight edges from u to v (by introducing new intermediate vertices).\ For example: edge (u, v) with weight w = 3 Figure from the original question paper Run **BFS** on this modified graph from the source s to find the shortest path to each of the original vertices in the graph.\ Which of the following statements is/are true?\ **I.** The algorithm solves the single source shortest path problem correctly.\ **II.** Although the size of the modified graph is larger than the original graph, the algorithm is as efficient as Dijkstra’s algorithm. What is the weight of a **minimum spanning tree** in the graph given below? Figure from the original question paper