Please help thanks For a graph with n vertices and m edges

Please help thanks !

For a graph with n vertices and m edges, how many iterations of the Bellman-Ford algorithm need to be run, in the worst case? n + 1 m n m + 1 1 n + 1 How many relax operations are run for each iteration of the algorithm? n relax operations 1 relax operation m relax operations m+1 relax operations m+n relax operations n+1 relax operations Which of the following situations will allow us to conclude that a given graph has a negative weight cycle? The distance estimate to some node is -infinity The distance estimates do not converge even after m-1 iterations Bellman-Ford algorithm can never detect a negative cycle in a graph The distance estimate to a node that is not the source a 0 Some node in the graph has a negative distance estimate The distance estimates do not converge even after n + 1 iterations Consider the graph below. We wish to compute all shortest paths starting from source node 0. If for each iteration, we consider the edges n the order below: How many iterations of the Beilman-Ford algorithm need to be run before terminates? For the graph above, can we run Dijkstra\'s algorithm to compute the shortest paths? Yes No

Solution

1)Ans is n-1 if there are no negative edges in graph at worst case.

2)N iterations of the outer loops causes us to relax every edge once,.Hence For each iteration of bellaman ford it takes m relax operation which is no of edges.

3)Some node in graph has negative distance.After performing N-1 loops if there is no change in distance array and there is no change in parent array then it has no negative cycle,But if distance array has negative value for node and parent array has different value then it has negative cycle.

4)Bellaman Ford runs for N-1 times .In above graph it has 6 vertices.so it will run for 6-1=5 times.

5)We cant use Dijkstra\'s on negative edges of graph .hence ,answer is NO