Go through every station and check if using it as an intermediate station gives better path
for ( $ i = 0 ; $ i < $ N ; $ i ++ ) for ( $ j = $ i + 1 ; $ j < $ N ; $ j ++ ) if ( $ dist [ $ j ] > $ dist [ $ i ] + $ cost [ $ i ] [ $ j ] ) $ dist [ $ j ] = $ dist [ $ i ] + $ cost [ $ i ] [ $ j ] ; return $ dist [ $ N - 1 ] ; }