Dogs can also eat Metamucil. The active ingredient is Psyllium, a bulk-forming laxative, used to treat constipation. Get the plain unflavored stuff and stir some (depends on the weight of the dog, but you don’t need too much) powder into the food (either the canned food recommended above, or plain yogurt which is also good for digestion).
Our doggie dietitian actually included it in the recipe we home-cook for our dogs, so they get it every night, and they do fine.