Algorithm
Q221.
Consider the weighted undirected graph with 4 vertices,where the weigh to edge {i, j} is given by the entry Wij in the matrix W. W=\begin{bmatrix} 0 & 2&8 & 5\\ 2& 0& 5 &8 \\ 8 & 5 & 0& x\\ 5&8 & x&0 \end{bmatrix} The largest possible integer value of x, for which at least one shortest path between some pair of vertices will contain the edge with weight x is ____.Q222.
In an unweighted, undirected connected graph, the shortest path from a node S to every other node is computed most efficiently, in terms of time complexity, byQ223.
Let G(V,E) be an undirected graph with positive edge weights. Dijkstra's single source shortest path algorithm can be implemented using the binary heap data structure with time complexity:Q224.
Consider the tree arcs of a BFS traversal from a source node W in an unweighted, connected, undirected graph. The tree T formed by the tree arcs is a data structure for computingQ225.
Let G = (V,E) be an undirected graph with a sub-graph G1 = (V1,E1), Weight are assigned to edges of G as follows w(e)=\left\{\begin{matrix} 0 &if \; e \in E, \\ 1& otherwise \end{matrix}\right. A single-source shortest path algorithm is executed on the weighted graph (V,E,w) with an arbitrary vertex v1 of V1 as the source. Which of the following can always be inferred from the path costs computed?Q226.
Suppose we run Dijkstra's single source shortest-path algorithm on the following edge-weighted directed graph with vertex P as the source. In what order do the nodes get included into the set of vertices for which the shortest path distances are finalized?Q227.
Which of the following statement(s) is/are correct regarding Bellman-Ford shortest path algorithm? P. Always finds a negative weighted cycle, if one exists. Q. Finds whether any negative weighted cycle is reachable from the source.Q228.
Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry W_{ij} in the matrix W below is the weight of the edge {i, j}. \begin{pmatrix} 0&1 & 8 & 1 &4 \\ 1& 0 & 12 & 4 & 9\\ 8 & 12 & 0 & 7 & 3\\ 1& 4& 7 & 0 &2 \\ 4& 9 & 3& 2 &0 \end{pmatrix}What is the minimum possible weight of a path P from vertex 1 to vertex 2 in this graph such that P contains at most 3 edges?Q229.
Consider a weighted, undirected graph with positive edge weights and let uv be an edge in the graph. It is known that the shortest path from the source vertex s to u has weight 53 and the shortest path from s to v has weight 65. Which one of the following statements is always TRUE?Q230.
Consider the undirected unweighted graph G. Let a breadth-first traversal of G be done starting from a node r . Let d(r,u) and d(r,v) be the lengths of the shortest paths form r to u and v respectively in G. If u is visited before v during the breadth-first traversal, which of the following statements is correct ?