Backtracking in A star

your image is like 2d grid map

But your text suggest graph approach which is a bit confusing.

• For 2D grid map the costs must be different between cells on path

You got too much of cost=100 in there and therefore you can not backtrack the path. You have to increase or decrease cost on each step and fill only cells that are near last filled cells. That can be done by recursion on big maps or by scanning whole map or bounding box for last filled number on small maps.

• Look here for mine C++ A* implementation

The backtracking

Can be done by scanning neighbors of start/end cells after A* filling moving always to the smallest/biggest cost

In this example start filling from (2,0) until (3,3) is hit and then backtrack from (3,2) cost=8 to the smallest cost (always cost-1 for incremental filling). If you need the path in reverse order then start filling from (3,3) instead ...

speedup

Sometimes double filling speed up the process so: Start filling from both ends and stop when they join. To recognize which cell is filled from which point you can use positive and negative values, or some big enough ranges for costs.