How to limit elevation over distance using the A search algorithm?

My application finds or constructs routes that are shortest for trekkers in a hilly/mountain terrain using the A* search algorithm. Input files are .dem (Digital Elevation Model) and a roadmap file that contains existing routes. Code is in Python, libraries used are pygdal, NumPy and PyQGIS.

The routes provided by the algorithm are very steep. I want my route to follow the gradient guidelines, like say for every 30m only 1m of elevation.

If I could put my objective in a more simpler way, then it is that using A* I can find the shortest route, but the problem with that it finds path from one peak of the mountain to the valley in a straight line, which is not practical. I want the output should descent from one contour line to another at less that a particular angle so that the descent is not so steep. In this case the recommended gradient descent is 1.91 degrees.