We present a fully Lagrangian conservation form of the general relativistic hydrodynamic equations for perfect fluids with artificial viscosity in a given arbitrary background spacetime. This conservation formulation is achieved by choosing suitable Lagrangian time evolution variables, from which the generic fluid variables rest-mass density, 3-velocity, and thermodynamic pressure have to be determined. We present the corresponding equations for an ideal gas and show the existence and uniqueness of the solution. On the basis of the Lagrangian formulation we have developed a three-dimensional general relativistic Smoothed Particle Hydrodynamics (SPH) code using the standard SPH formalism as known from non-relativistic fluid dynamics. One-dimensional simulations of a shock tube and a wall shock are presented. With our method we can model ultra-relativistic fluid flows including shocks with relativistic gamma-factors of even 1000.