Algorithm
Q231.
Let G=(V,E) be an undirected unweighted connected graph. The diameter of G is defined as: diam(G)=\displaystyle \max_{u,v \in V} \{ \text{the length of shortest path between }u \text{ and }v \} Let M be the adjacency matrix of G. Define graph G_2 on the same set of vertices with adjacency matrix N, where N_{ij}=\left\{\begin{array} {lcl} 1 &\text{if}\; M_{ij}>0 \text{ or } P_{ij}>0, \text{ where }P=M^2\\0 &\text{otherwise} \end{array}\right. Which one of the following statements is true?Q232.
What is the time complexity of Bellman-Ford single-source shortest path algorithm on a complete graph of n vertices?Q233.
Let s and t be two vertices in a undirected graph G=(V, E) having distinct positive edge weights. Let [X, Y] be a partition of V such that s\inX and t\inY. Consider the edge e having the minimum weight amongst all those edges that have one vertex in X and one vertex in Y. Let the weight of an edge e denote the congestion on that edge. The congestion on a path is defined to be the maximum of the congestions on the edges of the path. We wish to find the path from s to t having minimum congestion. Which one of the following paths is always such a path of minimum congestion?Q234.
To implement Dijkstra's shortest path algorithm on unweighted graphs so that it runs in linear time, then data structure to be used isQ235.
Dijkstra's single source shortest path algorithm when run from vertex a in the above graph, computes the correct shortest path distance toQ236.
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