> 2. Store metadata about the current a* search in the graph nodes themselves so you don't have to maintain in a separate associative array.

This might be suitable in some circumstances, but it mixes your hot & cold data, prevents concurrent searches from being performed. Personally I'd steer away from this without an extremely good reason.