For graphs with non-negative weights there is no particular


State whether the following statements are True/False giving a brief reason to justify each answer.

1. For graphs with non-negative weights, there is no particular advantage to using Dijkstra's algorithm vs Bellman-Ford's algorithm in solving the shortest paths problem.

2. Prim's algorithm is always asymptotically faster than Kruskal's algorithm.

3. Finding whether a graph contains a universal sink (i.e. a node that is reachable from all other nodes but has no outgoing edges) or not can be done in O(V^2) time using adjacency matrix representation.

4. Given a weighted directed graph with distinct weights, the shortest path between any two vertices will be unique.

5. Retrieving an element using hashing with collisions resolved by chaining takes O(1) time on the average.

Solution Preview :

Prepared by a verified Expert
Business Management: For graphs with non-negative weights there is no particular
Reference No:- TGS02566227

Now Priced at $10 (50% Discount)

Recommended (95%)

Rated (4.7/5)