Algorithm
Q231.
To implement Dijkstra's shortest path algorithm on unweighted graphs so that it runs in linear time, then data structure to be used isQ232.
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 ?Q233.
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:Q234.
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?Q235.
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?Q236.
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?