Algorithm to determine exchange rate

Question

Given a data set of various currency pairs, how do I efficiently compute the implied fx rate for a pair not supplied in the data set?

For example, say my database/table looks like this (this data is fudged):

GBP x USD = 1.5
USD x GBP = 0.64
GBP x EUR = 1.19
AUD x USD = 1.1  

Notice that (GBP,USD) != 1/(USD,GBP).

I would expect the following results:

print rate('GBP','USD')
> 1.5

print rate('USD','GBP')
> 0.64

print rate('GBP','EUR')
> 1.19

#now in the absence of an explicit pair, we imply one using the inverse
print rate('EUR','GBP')
> 0.84

These are the simple cases, it gets more interesting:

#this is the implied rate from (GBP,EUR) and (GBP,USD)
print rate('EUR','USD')
> 1.26

Or an even more complicated example is finding the most efficient translation using 3 or more pairs:

print rate('EUR','AUD')
> 1.38

I think that details the programming related aspects of this problem. I'd imagine there's an efficient or clever recursion that can be done here. The only requirement is that the least number of pairs are used to arrive at the asked for pair (this is to reduce error). If no explicit inverse is given, then inverting a pair costs you nothing.

Motivation
In the ideal financial world, currency markets are efficient. In reality, that's 99% true. Often times, odd currency pairs aren't quoted or they're quoted infrequently. If an explicit quote exists, we must use it in our arbitrary calculations. If not, we must imply the most accurate pair, out to as many decimal places as we can. Furthermore, they don't always multiply to 1 (actually, they never multiply to 1); this reflects the bid/ask spread in the market. So we keep as many pairs as we can in both directions, but would like to be able to code in general for all currencies.

I think I have a decent, brute force solution implemented. It works, but I thought the problem was interesting and was wondering if anyone else thought it was interesting/challenging. I'm personally working in Python but it's more an exercise than an implementation, so psuedo code is "good enough".

Answer 1

You're looking for the shortest path in a directed graph, where the currencies are the vertices and the given exchange rates are the edges. If an exchange rate is given only for one direction, you can add one for the opposite direction with a higher cost.