Minimum Spanning Tree

Question

1) Kruskal Algorithm

2) Prims Algorithm

3) Dijkstra Algorithm

4) Bellman Ford Algorithm

5) Floyd Warshall Algorithm

Among these which one works for only

i) Positive edge weight

ii) Negative edge weight

iii) Negative weight cycle

Answer 1

	Positive edge weight	Negative edge weight	Negative weight cycle
Kruskal Algorithm	YES	YES (Yes just add a positive number to all the edge weights which is sufficiently large to make all edge weights positive)	YES(Yes just add a positive number to all the edge weights which is sufficiently large to make all edge weights positive)
Prims Algorithm	YES	YES (Yes just add a positive number to all the edge weights which is sufficiently large to make all edge weights positive)	YES (Yes just add a positive number to all the edge weights which is sufficiently large to make all edge weights positive)
Dijkstra Algorithm	YES	NO(Not gives correct result always )	NO (can't detect negative weight cycles)
Bellman-Ford Algorithm	YES	YES	NO (But it can detect negative weight cycles)
Floyd Warshall Algorithm	YES	YES	NO (But it can detect negative weight cycles)

$\color{Magenta}{EDIT}$ -
Note - For those algorithms that can detect cycle, they cannot always detect $\color{RED}{ALL}$ the negative weight cycles. But they can always surely say that there is $\color{GREEN}{Some}$ negative edge weight cycle present in the Graph or not. 

Thanks a lot, @Deepak Poonia sir for suggesting edit.  :)

Comments

good ques https://gateoverflow.in/47185/dijkstra-algorithm

---

https://gateoverflow.in/1771/gate2014-1-11

---

T.C. of OBST

 

• $O(V^{3})$

 

T.C. of strongly connected component

 

• $O(V+E)$
• https://www.geeksforgeeks.org/strongly-connected-components/

 

 

Number of BFS traversal of a complete graph $n!$