We define higher-dimensional Dedekind sums that generalize the classical Dedekind-Rademacher sums as well as Zagier's sums, and we show how to compute them effectively using a generalization of the continued-fraction algorithm. We present two applications. First, we show how to express special values of partial zeta functions associated to totally real number fields in terms of these sums via the Eisenstein cocycle introduced by R. Sczech. Hence we obtain a polynomial time algorithm for computing these special values. Second, we show how to use our techniques to compute certain special values of the Witten zeta function, and we compute some explicit examples.