So basically you know that the string has to start with a sequence of character a. What you do is compute the "distance" for every cell in the grid as the minimum number of characters to get to that cell that are not a. The cells farthest away from the origin with our defined "distance" are potential starting points. Why? Because they're guaranteed to have the most a in the front of the string.

Ok, now we know the starting points, the remainder is not too bad. Just keep track of a list of the best letters at a certain distance from the origin, and greedily pick the smallest ones, then updating the list with the children of the smallest letters. Then if you do this to the end you have the minimum string.