Removing the obstacle that yields the best path from a map after A* traversal

I traverse a 16x16 maze using my own A* implementation.

All is well. However, after the traversal, I would like to find out what wall would give me the best alternative path. Apart from removing every block and re-running A* on the maze, what's a more clever and elegant solution?

I was thinking give every wall node (ignored by A*), a tentative F-value, and change the node structure to also have a n-sized list of node *tentative_parent where n is the number of walls in the maze. Could this be viable?