In Feynman's path integral formulation, what do faster-than-light paths mean? In Brian Greene's book "The elegant Universe", he talks about the double slit experiment and Feynman's interpretation of Quantum Mechanics. According to the book, Feynman said that one vaild interpretation is that on its way from the emitter to the photoscreen, the photon actually takes every possible path. Greene actually says that some paths include a trip to the Andromeda galaxy and back, as a photon takes (as said before) $\textit{every}$ possible path.
Now if this were really the case and we measure the time between the emission of a photon and its impact on the photoscreen, doesn't this mean that some photons would actually travel with a velocity far greater than the speed of light? If a photon actually travelled to Andromeda and back, there is no way it could  arrive at the photoscreen in just a fraction of a second as is observed during experiment....
 A: I would like to add a few things to ACuriousMind's answer. What Greene most certainly intends to say is every path(even faster than light ones i.e. those which are not time-like everywhere) contributes to the propagation amplitude. In fact,since every path in space-time contributes with equal weight, there are also paths which go "back in time" and "come forward" again. For these paths, at a given time, there are multiple positions for the particle which increases the number of degrees of freedom needed. This shows that the single particle picture is no longer consistent with special relativity and one needs infinite degrees of freedom. i.e. a quantum field theory. If you want to study this, you can follow this lecture series by T. Padmanabhan or you can look into his new book.
A: The paths of the Feynman path integral are not actually taken. The phrase "takes every possible path" is a mangled statement of the mathematical instruction to take the integral of $\exp(-\mathrm{i}S)$ over all possible paths for the action $S$ to get the probability amplitude of something happening. It is a fact of quantum mechanics that this integral computes the correct quantum mechanical amplitude, but the formalism of quantum mechanics never says anything about the particle "taking" these paths, which is in particular absurd because quantum objects are not point particles that have a well-defined path in the first place. So, well, you can say that it "takes" every possible path as long as you don't literally imagine a point particle zipping along each path. Which is what "taking" a path usually means. Which is why this figure of speech does not actually convey any physical insight. 
The physical insight lies in understanding how the path integral reproduces the correct quantum mechanical amplitude, which cannot be done on the level of such crude heuristic statements based on classical notions of "path" and "particle". There is no path a quantum particle takes unless you continually track it, and then you'll get a perfectly ordinary classical path (see, for instance, the perfectly normal paths in bubble chambers, where the continual interaction with the bubble chamber effectively tracks the particle).
A: 
According to the book, Feynman said that one valid interpretation is that on its way from the emitter to the photoscreen, the photon actually takes every possible path.

That's right. The photon has an E=hf wave nature. It is not a point particle. Think of it as something like a seismic wave. Imagine a seismic wave travelling from A to B on a gedanken plain. It isn't just the houses sitting on top of the AB line that shake. Houses well away from the AB line shake too. The further away they are, the less they shake. But they still shake. In the respect the seismic wave takes many paths. The photon is somewhat similar. Here's a depiction from Aephraim Steinberg's weak measurement article:


Greene actually says that some paths include a trip to the Andromeda galaxy and back, as a photon takes (as said before) every possible path.

Brian Greene is over egging it I'm afraid. As are those people who claim that there are also paths which go "back in time" and "come forward" again.

Now if this were really the case and we measure the time between the emission of a photon and its impact on the photoscreen, doesn't this mean that some photons would actually travel with a velocity far greater than the speed of light?

No. Photons travel at the speed of light. 

If a photon actually travelled to Andromeda and back, there is no way it could arrive at the photoscreen in just a fraction of a second as is observed during experiment.

Correct. 
