That's exactly what floating point numbers are: representations of real number intervals as finite length bit strings. The number of bits simply determines the granularity of the representation (ie. the width of the intervals).

Floating point numbers are approximations of real numbers, which isn't sufficient in this context. Solving a lossy representation of the problem isn't a reduction in the complexity theoretic sense.

In the case of this problem the set of possible paths is finite so it can, in principle, be sorted in order of increasing cost. The smallest cost delta between any 2 paths in the sorted list is the lowest cost edge in the graph (this probably assumes that all edge costs are positive) so you only need to continue the binary search until intervals of this size are reached. At that point the exact solution has been found.

EDIT: There might be multiple paths with the same minimal cost but binary search will still find this value.

That depends on how you define your representation. It is useful for some problems to represent an interval with it's first bits, e.g. to take 0.101 as representing all numbers in the [0.101, 0.110) interval.

You are correct. What I meant to say was: You cannot represent all the distinct real numbers in a nonempty interval using a finite number of bits.

Why is that relevant?

Fortunately, non-empty intervals of real numbers do not exist in computer science.

Did I get my mathematical terms wrong or are you confusing number representations on computers with computer science?

I choose the nonempty interval [0, 1]. I have just represented it here in 48 bits (many of which are unnecessary, but bits are cheap). I don't think your statement is correct.