Bissoy.com
Doctors Medicines MCQs Q&A

In a directed weighted graph, if the weight of every edge is decreased by 10 units, does any change occur to the shortest path in the modified graph?

In a directed weighted graph, if the weight of every edge is decreased by 10 units, does any change occur to the shortest path in the modified graph? Correct Answer 57

The shortest path will change in the modified graph. Suppose that the shortest path is of weight 21 and has 7 edges and there is another path with 4 edges and total weight 17. Now, the weight of the first shortest path is increased by 7*10 and becomes 21 + 70 and the weight of the second path is increased by 4*10 and becomes 17 + 40. So the shortest path changes to the other path with weight as 57.

Related Questions

Let G be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increased by the same value, then which of the following statements is/are TRUE? P: Minimum spanning tree of G does not change Q: Shortest path between any pair of vertices does not change
Consider a network with nodes 1, 2, 3, 4, 5 and 6. The nodes are connected with directed arcs as shown in the table below. The respective costs (in INR) incurred while traversing the directed arcs are also mentioned. Directed arcs  1 → 2 1 → 3 2 → 4 2 → 5 3 → 2 3 → 4 3 → 5 4 → 5 4 → 6 5 → 6 Cost (in INR) 3 9 3 2 2 4 8 7 2 2 The second shortest path from node 1 to node 6 (i.e. the path that has the second least total cost and does not use any part of the shortest path) has a total cost (in INR) of
What is the condition for a tree to be weight balanced. where a is factor and n is a node? >= a*weight and weight >= a*weight. b) weight >= a*weight and weight >= a*weight. c) weight >= a*weight and weight >= a*weight. d) weight is a non zero
Consider the directed graph shown in the figure below. There are multiple shortest paths between vertices S and T. Which one will be reported by Dijkstra’s shortest path algorithm? Assume that, in any iteration, the shortest path to a vertex v is updated only when a strictly shorter path to v is discovered.
Assuming value of every weight to be greater than 10, in which of the following cases the shortest path of a directed weighted graph from 2 vertices u and v will never change?
Weight of Arun is 4/7 of the weight of Bablu. Weight of Bablu is 1/2 of the weight of Ram. Weight of Ram is 4 times of the weight of Deep. Weight of Deepis 1/9 of the weight of Ankit. Whose weight is more than the weight of Deep but less than the weight of Bablu?
An operating system uses the Banker’s algorithm for deadlock avoidance when managing the allocation of three resource types X, Y, and Z to three processes P0, P1, and P2. The table given below presents the current system state. Here, the Allocation matrix shows the current number of resources of each type allocated to each process and the Max matrix shows the maximum number of resources of each type required by each process during its execution.   Allocation Max   X Y Z X Y Z P0 0 0 1 8 4 3 P1 3 2 0 6 2 0 P2 2 1 1 3 3 3   There are 3 units of type X, 2 units of type Y and 2 units of type Z still available. The system is currently in a safe state. Consider the following independent requests for additional resources in the current state: REQ1: P0 requests 0 units of X, 0 units of Y and 2 units of Z REQ2: P1 requests 2 units of X, 0 units of Y and 0 units of Z Which one of the following is TRUE?
The rate of electricity in the rural area is given below: i) up to 25 units - Rs 5 per unit ii) up to 75 units - Rs 7 per units iii) up to 100 units - Rs 9 per units iv) After 100 units - Rs 13 per units Additional charge after 100 units = Rs. 50 The consumption of the electricity of the household is 120 units. How much electricity bill he has to pay?
For the given conditions, which of the following is in the correct order of increasing space requirement? i) Undirected, no weight ii) Directed, no weight iii) Directed, weighted iv) Undirected, weighted
The line graph L(G) of a simple graph G is defined as follows: There is exactly one vertex v(e) in L(G) for each edge e in G. For any two edges e and e' in G, L(G) has an edge between v(e) and v(e'), if and only if e and e' are incident with the same vertex in G. Which of the following statements is/are TRUE? (P) The line graph of a cycle is a cycle. (Q) The line graph of a clique is a clique. (R) The line graph of a planar graph is planar. (S) The line graph of a tree is a tree.