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 ] ; } } } } }