ciudades = np.arange(6) ciudad=0 visitados = [ciudad] tabla_pesos = np.array([[c, np.inf] for c in ciudades]) tabla_pesos[ciudad,1] = 0 rutas_opt = {c:[] for c in range(6)} rutas_opt[ciudad] = [ciudad] while len(visitados)<6: pesos_ciud_cand = np.array([[c, A[ciudad,c]] for c in ciudades if c not in visitados]) for cand in pesos_ciud_cand: ind_cand = int(cand[0]) if cand[1] + tabla_pesos[ciudad,1] < tabla_pesos[ind_cand,1]: tabla_pesos[ind_cand,1] = cand[1] + tabla_pesos[ciudad,1] r_cand = rutas_opt[ciudad].copy() r_cand.append(ind_cand) rutas_opt[ind_cand] = r_cand best_ind = np.argmin(tabla_pesos[pesos_ciud_cand[:,0].astype(np.int32),1]) ciudad = int(tabla_pesos[int(pesos_ciud_cand[best_ind,0]),0]) visitados.append(ciudad)

O(n^2)