A pseudo code for Bellman Ford where each edge is relaxed k times where k>=1. Let the graph G be a simple connected and undirected graph . Let number of vertices be V, and number of edges be E .
int i=1;
for( i=1;i<=k;i++)
{
For each edge (u,v) in G
{
if( d[v] > d[u] +cost(u,v))
then d[v] =d[u] +cost(u,v)
}
}
// Now we relax every edge again to detect negative weight cycle
Where d[v] denotes the cost of shortest path from source S to node v, at any instant of time. Initially d[v]=0 if v=S else d[v] =infinite
Cost (u,v) denotes weight of the edge (u,v).
Which of the following statement is true.
(i) For any, k d[v] denotes the shortest path from source to node v using atmost k edges.
(ii) For proper running of the algorithm k can be equal to V-1.
(iii) For proper running of the algorithm k must be equal to E.
