Match List 1 with List 2 and choose the correct answer from the code given below:

List I

(Graph Algorithm)

List II

(Time Complexity)

a) Dijkstra’s algorithm

i) Θ(E log E)

b) Kruskal’s algorithm

ii) Θ(V³)

c) Floyd-Warshall algorithm

iii) Θ(V²)

d) Topological sorting

iv) Θ(V + E)

Where V and E are the number of vertices and edges in graph respectively.

Question

Question

This question was previously asked in

UGC NET Computer Science (Paper 2) Dec 2018 Paper

Attempt Online

Answer 1

Dijkstra's algorithm is an algorithm for finding the shortest paths between nodes in a graph and time complexity is O(V²).
Kruskal's algorithm is a minimum-spanning-tree algorithm which finds an edge of the least possible weight that connects any two trees in the forest.
A topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v,u comes before v.
Floyd–Warshall algorithm is an algorithm for finding shortest paths in a weighted graph with positive or negative edge weights. A single execution of the algorithm will find the lengths of shortest paths between all pairs of vertices.