At the fork in the road, the explorer has three possible directions she can take: left, right or back where she came from. She can therefore ask the native the following question: "Which of these three roads do not lead to the cannibals' village?"
The truth teller will point to two roads, including the road the explorer has come from. The liar will point just to the cannibals' village. Therefore, if the native points to just one road, the explorer should assume him to be a liar and take the other route. If the native point to two roads, the explorer should head off along the one of the two which she has not just come from.
Of course, as with all similar logic problems concerning liars, the question arises as to whether the nature of a compulsive liar is to always say what is least true, or simply to deceive. In the case of the latter, the problem would be impossible to solve.
See also THE LIAR PARADOX