Bissoy.com
Doctors Medicines MCQs Q&A

Let G(V, E) be a directed graph where every edge has weight as either 1, 2 or 5, what is the algorithm used for the shortest path from a given source vertex to a given destination vertex to get the time complexity of O(V+E)?

Let G(V, E) be a directed graph where every edge has weight as either 1, 2 or 5, what is the algorithm used for the shortest path from a given source vertex to a given destination vertex to get the time complexity of O(V+E)? Correct Answer BFS

In BFS due to the least number of edges between two vertices and so if all the edges in a graph are of same weight, then to find the shortest path BFS can be used for efficiency. So we have to split all edges of weight 5 into two edges of weight 2 each and one edge of weight 1. In the worst case, all edges are of weight 1. To split all edges, O(E) operations can be done and so the time complexity becomes which is equal to O(V+E).

Related Questions

Let D be a simple graph on 10 vertices such that there is a vertex of degree 1, a vertex of degree 2, a vertex of degree 3, a vertex of degree 4, a vertex of degree 5, a vertex of degree 6, a vertex of degree 7, a vertex of degree 8 and a vertex of degree 9. What can be the degree of the last vertex?
Let G be a directed graph whose vertex set is the set of numbers from 1 to 100. There is an edge from a vertex i to a vertex j if and only if either j = i + 1 or j = 3i. The minimum number of edges in a path in G from vertex 1 to vertex 100 is 
Let G be a directed graph whose vertex set is the set of numbers from 1 to 50. There is an edge from a vertex i to a vertex j if and only if either j = i + 1 or j = 3i. Calculate the minimum number of edges in a path in G from vertex 1 to vertex 50.
The question below consists of a set of labeled sentences. From the four options given, select the most probable sequence to form a coherent paragraph. A. He fiddles with a newspaper and a letter and that's when Ove notices it's the same youth who argued with him about that bicycle a few days ago. B. He looks like a waiter who.is undecided about whether to serve you your food or take it into the kitchen and spit on it. C. The youth barely manages to avoid being knocked off the steps when Ove throws the door open and gives him a surprised look. D. The youth looks even less thrilled about recognizing Ove than vice-versa.
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.
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.
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
Let G be a simple undirected graph. Let TD be a depth first search tree of G. Let TB be a breadth first search tree of G. Consider the following statements. (I) No edge of G is a cross edge with respect to TD. (A cross edge in G is between two nodes neither of which is an ancestor of the other in TD .) (II) For every edge (u, v) of if u is at depth i and v is at depth j in TB , then |? − ?| = 1. Which of the statements above must necessarily be true?
The question below consists of a set of labelled sentences. From the four options given, select the most probable sequence to form a coherent paragraph. A. It was a time of change in the country and people moved and found new jobs, bought televisions, and the newspapers started talking about a 'middle class'. B. Ove received several letters from the council about what was called the 'redrawing of municipal boundaries', which he didn't quite understand, but understood that his parental home didn't fit among the new-built houses in the street. C. The middle classes moved into new housing developments with straight walls and carefully trimmed lawns, and it soon grew clear to Ove that his parental home stood in the way of progress. D. The council notified him of their intention to force him to sell the land to them so the house could be demolished and another built in its place.