SSSP - Bellman-Ford

Question 1

Works with Negative weight

Answer 1

yes

Question 2

Time complexity

Answer 2

O(V*E) as we repeat V-1 times all edges

Question 3

Relax all edges by V-1 times

Answer 3

w(u) + w(u-v) <= w(v) then update with new weight

Question 4

Total number of edges in complete graph N

Answer 4

[n(n-1)]/2

Question 5

Set source vertex 0 and rest all as INFINITY

Answer 5

use relax method V-1 times

Question 6

Time complexity for complete graph

Answer 6

(nn-1/2) * (n-1)
n-1 nodes
(nn–1) / 2 edges
o(n)^3

Question 7

Will not work with Cycle with Negative weights

Answer 7

It will work for positive. But not for negative cycles
Normally weights will not change after V-1 times. But if changes then we have negative weight cycles

Question 8

How it works

Answer 8

Usually given source vertex, order of edges and number of passes.
If source vertex is not given then pick one run by keeping every edge as INFINITY and source 0
And repeat this with N-1 times
https://www.youtube.com/watch?v=FtN3BYH2Zes