The rewards the agent get from this environment is in this way: if the agent gets to G, it receives a reward of 1 and otherwise, it receives the reward of 0.
This is an unusual way to reward an agent for a search, as there is no incentive for it to get to the goal state in any given time. The expected return for random behaviour that gets to the goal after a million moves is 1, the same as the expected return if it gets to the goal in ten moves. All policies that get to the goal state eventually will have a value of 1 for all actions. That in turn means that a random policy is just as optimal as one that heads straight to the goal, so there is nothing useful to be learned.
You need to have either a discount rate, or a cost for taking time. I think the latter will be more effective when combined with TD learning in your case.
Assign a cost, or negative reward for each time step. Say $-1$ per time step. The reward for reaching the goal can be zero in that case. Getting a maximum (but negative) reward is then the same as finding the quickest route from the start to the goal.
the probability of getting to G by choosing random actions is almost zero.
If you use a Temporal Difference algorithm, such as Q learning, and set the initial return estimate for all $Q(s,a)$ to an optimistic value - e.g. $0$ - then the behaviour will not in fact be random. That is because in TD, the agent can learn from rewards it receives mid-episode. The agent will explore "promising" paths that it has not seen before, and be discouraged from states it has been to multiple times without completing the episode. If you visualise the agent on the first episode, you will see it move back and forth over different areas of the map as it exhaustively searches for a better reward than the repeated $-1$.
Depending on the size of the map, it could still take a long time, compared to, say an A* search based on heuristics. Even for simple problems, there is an element of brute-force searching in reinforcement learning. However, that is an unfair comparison, since you have withheld any heuristics from the agent, it has had to learn its own from testing the environment.
If a real-world problem allows you to add prior knowledge about the agent's goal, then the best way to incorporate that is to alter the initial Q estimates - e.g. you could make it similar to the heuristic that you would of fed to A*. You should avoid altering the reward to "help" the agent learn interim steps - instead the reward needs to be designed to formally describe the goal of solving the environment. In toy problems, you are often interested in setting arbitrarily difficult goals in order to see if a particular kind of agent can solve them.
You can improve learning speed further by using more advanced algorithms that combine TD learning with episodic Monte Carlo control. The Q($\lambda$) algorithm allows the agent to assign a portion of sampled reward to the history of previous states and actions, and this can help in environments with sparse reward.
