def shortest_path(ncost_nk,ecost_nkk):
    N,K = ncost_nk.shape
    cost_nk = np.empty((N,K),dtype='float')
    prev_nk = np.empty((N-1,K),dtype='int')
    cost_nk[0] = ncost_nk[0]
    for n in xrange(1,N):
        cost_kk = ecost_nkk[n-1] + cost_nk[n-1][:,None] + ncost_nk[n][None,:]
        cost_nk[n] = cost_kk.min(axis=0)
        prev_nk[n-1] = cost_kk.argmin(axis=0)

    cost = cost_nk[N-1].min()

    path = np.empty(N,dtype='int')    
    path[N-1] = cost_nk[N-1].argmin()
    for n in xrange(N-1,0,-1):
        path[n-1] = prev_nk[n-1,path[n]]
        
    return path,cost
ncost_nk: N x K
dataset/ETHPy150Open rll/lfd/lfd/rapprentice/retiming.py/shortest_path