Relax all edges | V | - 1 times .
for ( int i = 1 ; i <= V - 1 ; i ++ ) { for ( int j = 0 ; j < E ; j ++ ) { int u = graph -> edge [ j ] . src ; int v = graph -> edge [ j ] . dest ; int weight = graph -> edge [ j ] . weight ; if ( dist [ u ] != INT_MAX && dist [ u ] + weight < dist [ v ] ) { dist [ v ] = dist [ u ] + weight ; parent [ v ] = u ; } } }