Relax all edges | V | - 1 times . A simple shortest path from src to any other vertex can have at - most | V | - 1 edges
for ( $ i = 0 ; $ i < $ V - 1 ; $ i ++ ) { for ( $ j = 0 ; $ j < $ E ; $ j ++ ) { if ( $ dis [ $ graph [ $ j ] [ 0 ] ] != PHP_INT_MAX && $ dis [ $ graph [ $ j ] [ 0 ] ] + $ graph [ $ j ] [ 2 ] < $ dis [ $ graph [ $ j ] [ 1 ] ] ) $ dis [ $ graph [ $ j ] [ 1 ] ] = $ dis [ $ graph [ $ j ] [ 0 ] ] + $ graph [ $ j ] [ 2 ] ; } }