986 views

Match the following :

$\begin{array}{clcl} \text{a.} & \text{Prim’s algorithm} & \text{i.} & \text{$O(V^2E)$} \\ \text{b.} & \text{Bellman-Ford algorithm} & \text{ii.} & \text{$O(VElgV)$} \\ \text{c.} & \text{Floyd-Warshall algorithm} & \text{iii.} & \text{$O(ElgV)$} \\ \text{d.} & \text{Johnson’s algorithm} & \text{iv.} & \text{$O(V^3)$} \\ \end{array}$

where $V$ is the set of nodes and $E$ is the set of edges in the graph.

$\textbf{Codes :}$

1. $\text{a-i, b-iii, c-iv, d-ii}$
2. $\text{a-i, b-iii, c-ii, d-iv}$
3. $\text{a-iii, b-i, c-iv, d-ii}$
4. $\text{a-iii, b-i, c-ii, d-iv}$

option C

a-iii       b- i      c-  iv       d- ii
by

yes Option C is correct because  Bellman-ford algo- O(V^2 E) and Floyd warshall - O(V^3)...i enough to match the option.

how bellman ford complexity o(v^2e) please explain