We cannot travel through edge that doesn 't exist
if ( dis [ i ] [ k ] == INF dis [ k ] [ j ] == INF ) continue ; if ( dis [ i ] [ j ] > dis [ i ] [ k ] + dis [ k ] [ j ] ) { dis [ i ] [ j ] = dis [ i ] [ k ] + dis [ k ] [ j ] ; Next [ i ] [ j ] = Next [ i ] [ k ] ; } } } } }