We have studied the nonlinear propagation of dust ion-acoustic (DIA) waves in a dusty multi-ion dense plasma (with the constituents being degenerate, either non-relativistic or ultra-relativistic) and the propagation of such waves have been investigated by the reductive perturbation method. From the stationary solution of the Korteweg de-Vries (K-dV) equation and Burgers’ equation the nonlinear waves (specially, solitary and shock waves) have been found to be formed in the dusty plasma system under consideration. It has shown that the basic features of these waves are significantly modified by both the positive and negative ions and dust number densities, the degenerate of the constituents. The implications of our results have been briefly discussed.